알고리즘 - 백트래킹(Back tracking)에 대한 이해

백준 사이트를 통해 알고리즘 공부를 하던 중, 백트래킹에 대한 개념이 명확하지 않아 정리해봅니다.

이론은 SW expert academy에서, 실습은 백준에서 참고했습니다.

 

---

N-Queen 문제

N x N 체스판에서 N개의 퀸이 서로를 공격하지 못하게 배치하는 문제

 

백트래킹 기법이란?

• 해를 찾는 도중에 막히면(해가 아니면) 되돌아가서 다시 해를 찾아가는 기법
• 초기 상태에서 목표 상태로 가는 경로를 탐색하는 기법
• 최적화 문제와 결정 문제를 해결할 수 있음

 

결정 문제 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 yes or no로 답하는 문제

 

예) 미로찾기

미로에서 빠져나갈 경로가 존재하는가? -> 결정 문제

미로에서 최단거리로 나갈 수 있는 경로는 무엇인가? -> 최적화 문제

 

올바른 선택을 계속하면 목표 상태에 도달

 

상태 공간 트리란?

• 해를 찾기 위한 선택의 과정을 트리로 표현한 것
• 트리의 내부 노드는 최종 상태로 가는 중간 상태를 나타냄
• 트리의 단말 노드는 하나의 후보 해에 대한 최종 상태
• 모든 후보해들을 탐색해야 함

-> 깊이 우선 탐색하는 방법이 백트래킹 알고리즘의 기본 형태

 

여기서 백트래킹 기법은 해당 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음(가지치기)

-> 경우의 수가 줄어듦

 

N-Queen 문제에 적용

N이 8이라면?

모든 경우의 수는 64C8 = 약 44억

실제 해의 수는 92개

-> 브루트 포스로 시행할 경우 엄청난 경우의 수

 

백트래킹 기법은?

모든 후보해를 검사하지 않음

어떤 노드의 유망성 점검 후 유망하지 않다고 결정되면 해당 노드의 부모로 돌아감(back tracking)
유망성이란? 해당 노드를 포함한 경로가 해답이 될 수 없을 경우 유망하지 않다고함.

유망성이 없는 경로를 더 이상 고려하지 않음 (가지치기)

 

유망성 판단 방법은 해를 찾으려는 문제에 따라 달라짐

 

깊이 우선 탐색 - 총 155개의 노드를 방문

백트래킹 - 총 27개의 노드를 방문 ( 깊이 우선 탐색의 1/5 )

 

---

실습

백준 15650번: N과 M (2) https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

# N과 M (2) N & M (2)

"""
N개의 숫자에서 M개를 뽑아 수열을 만든다.
단, 수열은 오름차순
"""

from sys import stdin

#입력
N, M = map(int,stdin.readline().split())

#방문 여부와 수열을 저장할 리스트 생성
visited = [0]*(N+1)
seq = [0]*M

#백트래킹 알고리즘
def backtracking(index, n, m):
    #말단 노드에 도달하면 수열 출력
    if index == m:
        for num in seq:
            print(num, end=' ')
        print()
        return
    
    #이전 숫자보다 큰 숫자들에 대해 반복
    for num in range(seq[index-1],N+1):
        #이미 방문한 노드라면 넘어감
        if visited[num] or num==0:
            continue
        visited[num]=True
        seq[index]=num

        #재귀적으로 함수 호출
        backtracking(index+1, n, m)

        #방문 여부를 해제함 (다른 경로에서 재방문하기 위해)
        visited[num]=False

backtracking(0, N, M)