백준 #9663 N-Queen (파이썬)

문제 링크

백트래킹의 가장 대표격 문제라 할 수 있는 N-Queen 문제다.

백트래킹 = for문 + if문 + 재귀로 짠다는 점을 기억하자!

추가적으로 다음과 같은 최적화 기법이 들어있다.

1. 체스판을 N*N으로 만들지 않고, 그냥 row(또는 col)만 만드는 것. 어차피 N-Queen 문제에서는 같은 행에 두 Queen을 동시에 놓을 수 없기 때문에, row[i] = j의 방식으로 (i, j) 위치에 Queen이 있음을 표시할 수 있다.

2. Queen은 십자 뿐 아니라 대각선 이동 경로도 존재한다. is_valid 함수의 abs(row[cnt] - row[idx] == cnt - idx 부분이 대각선이 중복하는지 체크하는 조건인데, 위의 1번 최적화 기법보다도 더 생각해내기 어렵다.

• 2D 체스판으로 생각해본다면, cnt - idx는 행의 차를 나타내고, row[cnt] - row[idx]는 열의 차를 나타낸다. 하지만 row[cnt] - row[idx]는 음수도 될 수 있으므로 절댓값을 씌워준다. 즉, 대각선이 겹치는지 확인하려면 지금까지 놓았던 Queen에 대하여 각각, 행의 차만큼 열의 차이가 나는 건 아닌지 확인해보면 된다.

너무 클리셰고 최적화 기법도 많이 들어있으니, 시간 나면 외우자.

# N-Queen 어떻게 풀더라
# Backtracking = for문 + if문 + 재귀

N = int(input())
row = [0] * N # 어차피 같은 row에 2개는 못 놓으니까, row[i] = j라면 (i, j)에 Queen이 있는 것
rv = 0

def is_valid(cnt):
    for idx in range(cnt):
        if row[cnt] == row[idx]:
            return False
        if abs(row[cnt] - row[idx]) == cnt-idx: # 이 조건 생각하는 게 어렵. 대각선 중복 조건
            return False
    return True

def backtrack(cnt):
    global rv 
    if cnt == N:
        rv += 1
        return
    for idx in range(N):
        row[cnt] = idx
        if is_valid(cnt):
            backtrack(cnt+1)

backtrack(0)
print(rv)