[백준] 9663번: N-Queen

이번 문제는 백트래킹의 대표적인 문제인 n-queen 이다. 체스에서, 퀸은 자신이 속한 가로줄, 세로줄, 대각선 줄안에 있는 모든 칸을 공격할 수 있다.

N*N 체스판에 N개의 퀸을 서로 공격 불가하게 놓는다고 생각을 하면 가로줄을 기준으로 한 줄에 한 개씩 올려놓으면 된다는 걸 알 수 있다. 이번 문제는 재귀함수로 한 줄씩 퀸을 놓는데, 놓으면 안되는 줄을 배제하는 과정(백트래킹: 이전에 퀸을 놓은 줄에는 놓으면 안됨)이 있다. 코드를 보자.

N = int(input())
cols = [-1 for _ in range(N)]

def solve(row, N):
    global ans
    if row == N:
        ans += 1
        return
    for col in range(N):
        can = True
        
        # 백트래킹
        for preRow in range(row):
            if col == cols[preRow] or abs(preRow - row) == abs(cols[preRow] - col):
                can = False
                break
                
        if can:
            cols[row] = col
            solve(row+1, N)
ans = 0
solve(0, N)
print(ans)

배제 조건 2가지

1. col == cols[preRow]: 0번부터 row-1까지 cols에 저장된 숫자들은 이번 줄에서 퀸을 놓을 수 없는 column의 idx이다. (같은 세로줄)

2. abs(preRow - row) == abs(cols[preRow] - col): 대각선에 이미 놓여져있으면 그 칸에 놓을 수 없다.

---

이번 문제는 이전의 답을 계속 순서에 따라 참조해야하기 때문에 Boolean 값으로 저장하기보단 답 자체를 저장하는 게 좋은 것 같다. 백트래킹 문제가 다 이런지는 다른 것들을 좀 더 풀어봐야 알 수 있을 것 같다.