Backtracking
백트래킹은 완전 탐색의 한 종류로 "가능한 모든 방법을 탐색한다"의 아이디어를 가지며 해를 찾는 도중 해가 아니어서 막히게 되면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다.
방식에 따라 깊이우선탐색(DFS)과 너비우선탐색(BFS), 최선 우선탐색(Best First Search, BFS)을 사용합니다. 경우의 수 구하기는 일반적으로 DFS가 편리합니다. 대다수의 문제들은 DFS를 써도 일단 답이 나오게 된다고 합니다.
아주 간단한 예제를 보면서 이해해 봅시다.
홀짝 만들기
문제. A,B,c 세 사람이 가지고 있는 숫자를 차례대로 하나씩 줄 세웁니다. 단, 조건은 짝수나 홀수가 연속으로 2번 나오면 안됩니다. 이 때, 만들 수 있는 숫자를 모두 구하시오.
-
가능한 경우의 수들
A - 1, B - 4, C - 7
A - 1, B - 4, C - 8
A - 1, B - 4, C - 9
등등 -
구현
-
A,B,C의 숫자들을 차례로 담아 2차원 배열로 넣어줍니다.
[[1,2,3], [4,5,6], [7,8,9]] -
현재 단계를 나타내는 depth와 숫자들을 기억할 history를 파라미터로 구현합니다.
-
DFS 함수를 작성합니다.
- depth를 이용해 현재 깊이를 저장합니다.
- depth가 numbers의 크기까지 왔다면 조건에 맞았다는 의미이므로 history를 출력합니다.
- 만약 history가 비어있을 경우 가장 첫번째(A)이므로 history에 숫자를 A의 숫자를 넣어주고 depth에 1을 더해 재귀를 합니다.
- 만약 history가 비어있지 않다면 현재 depth의 숫자들을 순회하며 history의 맨 마지막 숫자와 현재 숫자가 홀, 짝이 연속되지 않으면 추가해서 depth를 1 더합니다.
- 위 과정을 통해 탐색이 끝났을 때, history를 출력해줍니다.
import copy def dfs(numbers, depth, history): if depth == len(numbers): print(history) return # history가 비어있을 경우 if not history: for n in numbers[depth]: temp = copy.deepcopy(history) temp.append(n) dfs(numbers, depth+1, temp) else: # 비어있지 않은 경우 for n in numbers[depth] # 마지막 수가 홀수, n이 짝수이거나 마지막이 짝, n이 홀수인 경우 if (history[-1] % 2 == 0 and n % 2 != 0) or (history[-1] % 2 != 0 and n % 2 == 0): temp = copy.deepcopy(history) temp.append(n) dfs(numbers, depth+1, temp) numbers = [[1,2,3], [4,5,6], [7,8,9]] dfs(numbers, 0, [])출력
-
백트래킹 문제해결의 원리
백트래킹을 위해서는 우선 주어진 문제를 비선형 구조로 구조화하는 것이 중요합니다. 비선형으로 구성된 자료 구조를 DFS로 탐색할 때, 더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복귀하게 됩니다.
백트래킹 절차
-
DFS 수행
원래대로 재귀 호출을 이용해서 계속 이동하는 DFS를 수행해 노드를 찾습니다. -
유망한 노드 검토
방문한 노드를 포함해서 유망한 노드이면 서브트리로 이동하고 그렇지 않으면 백트래킹을 수행합니다. -
서브 트리 이동
방문한 노드의 하위 노드로 이동해 다시 재귀를 통해 DFS를 수행한다. -
백트래킹 수행
방문한 노드를 가지치기(Purning)하고 상위 노드로 백트래킹 한 후 DFS를 다시 수행한다.
이후의 숙련도는 아래 추천문제를 풀면서 올려봅시다!
[백준 추천문제]
1182(부분집합의 합)
1759(암호 만들기)
15649(N과 M(1))
1987(알파벳)
9663(N-Queen)
2580(스도쿠)
10597(순열장난)
2661(좋은수열)
17136(색종이 붙이기)
1189(컴백홈)
1405(미친로봇)
1339(단어수학)
[참고]
https://fomaios.tistory.com/entry/Algorithm-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9Backtracking%EC%9D%B4%EB%9E%80
https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220786417910&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList
