백트래킹 알고리즘 정리(feat. 백준 15649번 파이썬 풀이)

정의

모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것

 

 

DFS(깊이 우선 탐색) + 특정 조건만 탐색

깊이 우선 탐색의 애니메이션 예시

 

 

 

특징

1. 조건들을 하나씩 대입해가면서 만약 조건에 맞지 않는다면 그 즉시 중단하고 다음으로 넘어간다.

2. 상태공간트리를 DFS(깊이우선탐색)으로 탐색한다.

3. 방문 중인 노드에서 더 하위 노드로 가면 해답이 없을 경우, 해당 노드의 하위 트리를 방문하지 않고 부모 노드로 되돌아간다.

 

 

가치치기(pruning)

 - 유망하지 않으면(하위 노드가 답이 없을 경우) 하위 트리를 방문하지 않는 것.

---

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

 

 

정답풀이

#백트레킹
#N과 M(1)


N,M = map(int,input().split())

num_list = [i+1 for i in range(N)]
check_list = [False] * N

arr = []

def dfs(count):
    #print(arr)
    if count == M:                                                                           
        #원소만 빼서 출력하는것 * 
        print(*arr)
        return
    
    for i in range(N):
        #print("for i : -------",i)
        if check_list[i]:
            #print("중복이라 continue",check_list)
            continue
    #i번쨰는 거쳐갈것이기에 True
        check_list[i] = True
        arr.append(num_list[i])
        #print("append 이후",arr)
        #print(check_list)
    #현재의 i를 기준으로 가지치기
        dfs(count + 1)
       # print("재귀함수끝", i,count)
        arr.pop()
        #print("pop이후",arr)
        check_list[i] = False

dfs(0)

 

Q)check_list는 왜 [False] * N 인가?

 ->dfs 탐색을 하면서 중복되는 것을 체크하기 위해 기본 설정값을 False로 하는 것이다.

 

Q)for문은 왜 저렇게 설계되어있는가?
 ->N = 3 , M = 2인 경우를 생각해보자. 백트레킹 알고리즘은 어떻게 동작할까

결론만 말하자면 중복부분(빨강)에서는 stop하고 중복되지 않은 부분에서는 계속 진행할 것이다. 이제 코드를 하나하나 살펴보자.

 

dfs(0)에서 for i in range(N) 에서 i = 0 일 때

check_list[0] = True , arr.append(num_list[0])으로 인해

 

재귀함수 dfs(1)은 기본 값이 

check_list = [True,False,False] , arr =[1]인 상태로 시작하게 된다.(dfs(1)부터 코드가  실행중이므로 아직 dfs(0)에서의 arr.pop(), check_List[i] = False 실행 전)

 

 

이제  dfs(1)에서 for i in range(N)이 돌면서 i  = 0일 때를 생각해보자

check_list[0] == True 이므로 조건문이 성립되어 continue 된다. ( 중복이므로 제외한다. 사진의 빨간 부분)

 

 for i in range(N)이 돌면서 i  = 1일 때를 생각해보자

 check_list[1] == False 이므로 조건문이 성립되지 않고, 아래 코드가 실행된다.

중복 체크를 하기 위해 check_list[1] == True가 되고 arr = [1,2]가 된다. 이 값을 default로 

dfs(2)가 실행되게 되는데 이때에는 if(count == M)이므로 1 2를 출력하게 된다.

 

dfs(2)에서의 재귀함수가 하나 끝났으므로 밑의 arr.pop() check_list[1] = False코드가 동작하여

dfs(1) ▼

arr [1, 2] -> arr [1]

check_list [True,True,False] -> check-_list [True,False,False]로 바뀐 상태로 i =2 일때를 체크하게 된다.

 

dfs(1)에서 i =2 일때 마찬가지로 1 3 을 출력하게 된다.

 

dfs(1) 일때 for 문의 i = 0 에서의 재귀 호출은 모두 끝이 났으니 , 이제 아래 코드인 arr.pop(), check_list[i] = False가 실행되어

 

arr [1] -> []

check_list [True,False,False] -> check_list [False,False,False]가 된상태로

dfs(0)일 때의 i =1 for문 코드를 읽게 된다.

 

이런 식으로 진행하면

1 2
1 3
2 1
2 3
3 1
3 2

라는 값이 도출된다.

 

 

반드시 알아야할 점

*재귀함수는 실행하면 밑의 코드를 읽지 않고 재귀함수가 끝날 때까지 실행된다.

즉 그 깊이를 끝까지 탐색하고 나서야 종료되므로, 이 부분에서 헷갈리지 말자.