백트래킹(Backtracking) [Algorithm #2]

DFS(깊이 우선 탐색)의 경우 모든 경우의 수를 하나씩 다 따지기 때문에 매우 비효율적이다. 그래서 탐색 도중 조건에 맞지 않으면 이전 단계로 되돌아가는 백트래킹을 많이 이용한다.

중간중간 조건에 맞지 않는 케이스는 "가지치기"하여 탐색 시간을 줄인다.

이전 단계로 돌아가는 설계를 잘 해야 한다. 어떤 조건에 되돌아가게 할 건지, 어떤 시점으로 되돌아가게 할 건지를 잘 생각해야 한다.

 

코드 구현은 DFS처럼 재귀(Recursion)를 이용하되, 코드 도입부에 조건을 추가하여 조건에 맞지 않을 경우 return하여 이전 노드로 다시 되돌아가도록 구현하는 것이 일반적이다. 

 

def backtracking(...):	
    if ...: # 되돌아가는 조건
    	return
    for i in range(...): 
    	list.append(i) # stack에 push
        backtracking(i) # Recursion
        list.pop() # stack에서 pop

 

대표 예제를 살펴 보자.

https://www.acmicpc.net/problem/15649

# N과 M (1) : BOJ #15649

 

 

num_list=[]

def solution():
	if len(num_list) == M: # 길이가 최대가 되면 돌아가기.
            print(num_list) # num_list 모두 출력!!
            return
    for i in range(1, N+1):
    	if i not in num_list: # 없으면 stack에 push => num_list에 중복없이 들어가게 됨.
            num_list.append(i)
            solution()
            num_list.pop(i)

 

배열의 처음과 끝 조건을 잘 확인하는 것 잊지 말자.

 

삼전백준 #14889와 N-Queen 문제가 대표적인데, 직접 풀어서 코딩테스트에 포스트하겠다. 화이팅..!