작심 365
Backtracking에 대해서.. 본문
0/1 Knapsack과 같은 어려운 문제를 풀때 실질적으로 Dynamic Programing과 Brute Force 중 누가 더 낫다고 할 수 없다.
그렇다면 다시 Brute Force로 돌아와서 생각해보면 Brute Force를 구현하는 방법은 대표적으로 다음 두가지가 있다.
1. For loop
2. Graph 탐색 (DFS, BFS)
여기서 두번째 Graph 탐색에서 DFS 를 활용해 State-Space Tree를 가지고 생각해 보자.
간단한 문제 하나를 가지고 State Space를 직접 그려보자.
<동전 2개의 모든 조합을 나열하는 방법>
Tree의 가장 마지막 leaf node들이 바로 모든 경우를 나타내게 된다.
이제 백트래킹 문제의 가장 대표적인 문제인 N-Queen 문제를 보자
N-Queen 문제는 NxN 크기의 체스판 위에서 N개의 Queen을 서로 공격하지 못하는 위치에 두는 방법의 개수를 구하는 문제이다.
(Queen은 상,하,좌,우,대각선을 모두 공격할 수 있다)
문제를 어떻게 풀지 감이 안잡히지만 예제를 쉽게 만들어서 생각해 보면 아이디어가 떠오른다.
N을 4라고 생각하고 문제를 풀어보자.
Brute Force 방식으로 푼다면 4x4 = 16 개의 칸에 4개를 놓는 경우의 수. 즉, 16C4 를 다 확인해야 한다.
따라서 모든 경우의 수를 다 확인하다고 하면 시간 복잡도가 exponential 하게 증가한다.
하지만 우리는 모든 경우를 다 확인할 필요가 없다.
하나의 예시로 체스판에 하나의 행에는 한개의 퀸만 놓을수 있다. 퀸은 수평으로 공격이 가능하기 때문에 한 행에는 반드시 한개만 와야한다.
또 첫번째 행에 첫번째 열에 퀸이 놓여있다면 두번째 행에 첫번째 열을 놓는 경우는 굳이 확인할 필요가 없는 것이다.
즉, 우리는 모든 경우를 다 볼필요가 없이 탐색이 가능한 조합만 검사를 하면 된다.
그리고 이렇게 아예 가능성이 없는 곳은 더이상 탐색을 하지 않는것을 백트래킹 이라고 한다.
즉 State-Space Tree 에서 가능성이 없는 하위 노들은 더이상 확인하지 않도록 가지치기를 하는 것이다.
백트래킹으로 풀기
4-Queen 문제를 백트래킹을 적용해서 풀어보자.
우선 한 행에는 최대 한개의 퀸만 올라갈 수 있기때문에 각 행에 어느 열에 퀸을 놓을지 확인하면 된다.
4x4 격자판과, 상태 트리를 그리면 다음과 같다.
여기서 가장 먼저 Q1을 1.1 자리에 두었다고 가정하고 나머지 퀸들을 놓아보면 2.1과 2.2 자리는 놓을 수가 없다.
그럼 Q2를 2.1과 2.2에 놓는 조합들은 확인할 필요가 없게된다. 그럼 우리는 이때 다시 부모 노드로 백트래킹을 하게 되고 다시 Q2 그 다음 자리인 2.3에 둘 수 있다.
Q1를 1.1 , Q2를 2.3에 두었을때 Q3은 그 어디에도 둘 수 없기 때문에 다시 백트래킹 하게 된다.
결국 Q2를 2.3에 두는 것은 틀린 조합이 되는 것이므로 Q2를 2.4에 두고 다시 Q3과 Q4의 자리를 찾아야 한다.
Q1 을 1.1 , Q2를 2.4에 두었을때 Q3은 3.1은 불가능하고 3.2에 놓을 수 있다. 하지만 이때 Q4는 그 어느 위치에도 놓을 수 없다.
그러면 Q3의 위치를 다시 두어야 한다는 소리인데 Q3를 남은 3.3과 3.4에는 둘 수가 없으므로 결국은 가장 첫번째 노드인 Q1을 놓는 곳으로 백트래킹하여 Q1을 다음 위치인 1.2에 두고 다시 시작해야 된다.
맨 위에 4x4 격자판 그림처럼 Q1을 1.2에 두었을때는 답을 찾을 수 있다.
이런식으로 가능성이 없는 조합은 일찍이 가지치기를 하면 탐색하는 시간을 줄일수 있다.
이렇게 푸는 방법을 백트래킹 이라고 한다.
백준 N-Queen 문제
https://www.acmicpc.net/problem/9663
# x 번째 행에 놓은 queen 에 대해서 검증
def check(x):
# 이전 행에서 놓았던 모든 퀸들을 확인한다.
for i in range(x):
if row[x]==row[i]: # 위쪽 확인
return False
if abs(row[x]-row[i])==x-i: # 대각선 확인
return False
return True
# x 번째 행에 대하여 처리
def dfs(x):
global result
if x==n:
result +=1
else:
# x번째 행의 각 열에 퀸을 둔다고 가정
for i in range(n):
row[x]=i
if check(x): # 실제로 이 위치에 두어도 괜찮은지 확인
dfs(x+1) # 다음 행으로 넘어감.
n = int(input())
row = [0]*n
result = 0
dfs(0)
print(result)
백트래킹 정의
→ DFS of a tree except that nodes are visited if promising.
→ Do a DFS of a state-space tree, checking whether each node is promising, if it is non promising, backtracking to the node's parent.
설계 핵심
백트래킹의 핵심은 promising function을 설계하는 것이다.
N-Queen 문제의 경우는 promising function이 명확히 주어진다. 하지만 대부분의 경우 promising function을 우리가 직접 찾아내야 한다. 그리고 그것을 찾는게 어려울 수록 문제 난이도가 올라간다.