[Python] BOJ 9663 - N-Queen

https://www.acmicpc.net/problem/9663

9663번: N-Queen

# 백트래킹 문제중에 가장 대표적인 문제이다. (well-known)

 

 

1. 우선 한 행마다 하나씩 Queen을 놓음으로써 같은 행을 확인하는 작업은 하지 않아도 된다.

    N을 입력받고 col_set, diag_set1, diag_set2을 set으로 선언해준다.

    col_set은 Queen이 놓여져있는 열을 나타내고 diag_set1은 Queen이 놓여져있는

    왼쪽대각선을 나타내고 diag_set2는 Queen이 놓여져있는 오른쪽 대각선을 나타낸다.

 

2. 반복문을 돌며 (0, 0)부터 (0, N-1)까지 첫번째 행에 Queen을 놓으며 백트래킹을 실행한다.

 

3. BT함수(BackTracking)

    3-1. 만약 row나 col이 N이라면 배열범위를 벗어나므로 return해준다.

            현재 Queen을 놓으려는 col이 이미 col_set에 있다면 그 열에는 이미 Queen이 있으므로 return해준다.

            diag_set1, diag_set2도 마찬가지이다.

    

    3-2. Queen을 놓을 수 있지만, N이 cnt에 도달한 경우 N개의 Queen을 놓은 것이므로 

             answer를 1증가시키고 return해준다.

 

    3-3. col_set에 현재 열을 add해주고 diag_set1에 현재 (행-열), diag_set2에 현재 (행+열)을 넣어준다.

            반복문을 돌며 다음행에 0번째 열부터 N-1번째 열까지 BT함수를 재귀적으로 실행한다.

            BT함수를 실행한 뒤, 위에서 넣어주었던 col, (row - col), (row + col)을 remove해준다.   

 

def BT(row, col, cnt):
    global answer
 
    if row == N or col == N:
        return
    if col in col_set:
        return
    if (row - col) in diag_set1:
        return
    if (row + col) in diag_set2:
        return
 
    if cnt == N:
        answer += 1
        return
 
    col_set.add(col)
    diag_set1.add(row - col)
    diag_set2.add(row + col)
    for i in range(N):
        BT(row+1, i, cnt+1)
    col_set.remove(col)
    diag_set1.remove(row - col)
    diag_set2.remove(row + col)
 
N = int(input())  
answer = 0
col_set, diag_set1, diag_set2 = set(), set(), set()
for i in range(N):
    BT(0, i, 1)
print(answer)

(solved.ac 티어: 골드 5)

 

# 재귀, 백트래킹부분이 아직 약한데, 열심히 해보자!