백트래킹

단어 그대로 자식 노드의 유망성을 판단한 뒤 해당 노드가 유망하지 않다면 부모 노드로 돌아가 다른 자식 노드를 찾는 방법이다.

1. DFS와 백트래킹

그래프 탐색 기법 중 하나인 DFS와 백트레킹의 차이를 먼저 알아보기 위해 예시를 한번 보자.

• 0 <= a, b, c, d <= 100
• a+b+c+d = 30 이 되는 a, b, c, d 를 모두 구하여라.

이 경우 0 부터 시작해서 모든 조합을 찾아나갈 것이다.

• a = 10 이라도 b = 0 ~ 100, c = 0 ~ 100, d = 0 ~ 100 이 될 수 있다.

이러한 모든 경우의 수를 찾아서 탐색하는 것이 DFS 이다.
백트레킹의 경우를 찾아보자.

• 만약 a = 10 이라면 b는 0 <= b <= 20 이 된다.
• b = 21 이라면 그 이상은 탐색할 필요가 없어지게 되고 다음으로
• a = 11 일때 b, c, d 의 경우를 찾는 절차를 밟게 된다.
  

백트레킹은 이와 같이 유망하지 않은 노드의 경우 탐색을 중단하고 부모노드로 되돌아가게 된다.

정리하자면 다음과 같다.

• 백트레킹은 탐색가능한 모든 경우의 수 중 특정 조건을 만족하는 수만 탐색하는 것이다.
• 즉 답이 될만한지 판단하고 그렇지 않을 경우 유망하지 않은 경우 가지치기를 하는 것이다.
  
  
• 백트레킹 문제는 DFS의 과정에서 조건을 주며 절대 답이 되지 않을 상황을 정의하고, 그 상황의 경우 탐색을 중단하고 다시 부모 노드로 돌아가 다른 경우를 탐색하게 끔 한다.

2. 문제 설명

• 말 그대로 N×N 체스판에서 N개의 퀸이 서로 공격할 수 없게 놓는 것이다.
• 퀸은 아래와 같이 움직인다.

3. 문제 풀이

• 예시로 아래는 4×4 체스판에 퀸 4개가 공격할 수 없게 나두는 경우의 하나이다.

• 가장 좌측열에서 부터 하나씩 비교하며 해당 열의 모든 행에 퀸이 있는지 확인한다.

• 각 행을 체크할 때, 퀸이 없다면 유망한 후보로 고르고 해당 행 전체에 퀸이 있는지 조사한다.

• 이 또한 체크되었다면, 대각선을 확인한다.

• 이 과정을 통해 3행까지 확인이 된다면 다음 퀸은 3행 2열에 배치될것이다.

• 하지만 이 경우 다음은 어떠한곳도 퀸을 배치할 수 없다. 그렇다면 다시 2행으로 돌아가 다른곳에 배치하게 될 것 이다.

• 이 경우도 놓을 수 없으므로 1행으로 돌아가 다시 퀸을 배치하게 된다.
• 이 과정을 반복할 경우 완성되는 체스판은 아래와 같게 된다.

4. 코드

import sys
input = sys.stdin.readline

def is_promising(S):
    for i in range(S):
    	# 같은 열과 행에 있으면 안되고, # 대각선에 있으면 안되며, 1칸 차이가 나도 안된다.
        if l[S] == l[i] or abs(l[S]-l[i]) == S-i:
            return False
    return True

def Queen(S):
    global ans
    if S == N: # 끝줄까지 탐색 했으면
        ans += 1
    else:
        for i in range(N):
            l[S] = i
            if is_promising(S):
                Queen(S+1)
                
N = int(input())
ans = 0
l = [0]*N

Queen(0)
print(ans)

5. 후기

• 이 문제.. 백트레킹의 정석 문제라고 불린다.
  난 이 문제를 풀며 상당한 고통을 느꼈다. 여러번의 최적화 끝에 조건문을 간단히 작성하여
  is_promising 함수를 완성했다.
  백트레킹은 여러 방법이 있는 것 같다. 다른 문제를 풀다보니
  DFS에 백트레킹이 있는것이 아니라 백트레킹 안에 DFS가 있는 느낌이다.