[탐색/백트래킹] 백준 9663 N-Queen - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

9663번: N-Queen

 

 

 

2. 문제 풀이

 가로 세로 대각선에 겹치지 않게 N개의 퀸을 놓는 가짓수를 구하는 문제입니다.

 

2022.03.20 - [Algorithm] - [Algorithm] 백트래킹(Backtracking): 안될 싹은 미리미리 가지치기

[Algorithm] 백트래킹(Backtracking): 안될 싹은 미리미리 가지치기

 백트래킹 문제로, DFS탐색 중 다른 퀸에 겹치는 곳은 탐색하지 않습니다. 

 

 

 

3. 코드

# 입력
N = int(input())
board = [0]*N # 보드판
res = 0

# DFS 탐색
def dfs(x):
    global res # N개의 퀸을 놓는 경우의 수

    # 보드판 맨 끝에 도달해서 탐색마침(N개의 퀸 놓는 가짓수 +1)
    if x == N:
        res += 1
        return

    # 아직 탐색할 row가 남음
    else:
        # 해당 row의 1~N열 칸을 탐색
        for i in range(N):
            # x행, i열 탐색
            board[x] = i
            # 해당 칸이 다른 퀸이 겹치지 않는지 판별
            if isPromising(x):
                dfs(x+1)  # 겹치지 않으면 다음 행으로 이동

 DFS 탐색으로 각 경우의 수를 체스판의 맨 끝 줄까지 탐색합니다.

 어차피 행 별로 Queen은 최대 1개이며, 어느 열에 퀸을 놓는지가 중요하므로 board[x] = i로 행과 열을 저장합니다. (x행 i열에 Queen이 있다)

 (1,1)부터 (N,N)까지 탐색하며, 이전에 놓았던 퀸이랑 겹친다면 해당 칸의 탐색은 마치고 다음 칸으로 넘어갑니다.

 

 

# 백트래킹
def isPromising(x):
    for i in range(x):
        # 다른 퀸과 열이 같거나, 대각선이면 False
        if board[x] == board[i] or abs(board[x] - board[i]) == x-i:
            return False
    return True

# 출력
dfs(0)
print(res)

 백트래킹에서는 다른 퀸과 열이 같거나 대각선으로 만나는지를 판별합니다. 행과의 차이와 열과의 차이가 같으면 '같은 대각선' 위라는 뜻입니다.

 

 

cf) 여담

: 파이썬으로는 시간초과를 벗어날 수 없다... 결국은 N이 1~15일 때의 정답값을 모두 계산한 후에 찾아서 출력하는 방식을 써야 합니다. 저도 백준 정답 코드를 둘러보는데, 모두 같은 코드라서 놀랐어요 ㅋㅋㅋ

 

# 주저리주저리 푼 코드 써둬도, 정작 답 제출은 아래 코드로...
ans = [0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596, 2279184]
print(ans[int(input)])