[백준(파이썬/Python)] 9663_N-Queen - 백트랙킹

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

9663번: N-Queen

 

N-Queen 문제는 N*N 체스판에 상하좌우, 대각선에 퀸이 존재하지 않도록 적절히 퀸을 위치하는 문제입니다. 백트랙킹으로 풀 수 있는 대표적인 문제죠.

 

이 문제는 시간 제한이 상당히 타이트한데, 파이썬으로 제출할 경우 이차원 배열을 쓰면 당연히 시간초과가 나고 최적화를 해서 제출해야만 정답 판정을 받을 수 있습니다...ㅠㅠ

 

문제를 푸는 아이디어는 다음과 같습니다.

 

1. 각 행마다 Queen은 하나만 존재해야 하므로, 맨 위 행부터 내려오면서 백트랙킹을 구현한다.

2. 각 행에서 이전 행들을 관찰하면서 같은 열이나 대각선에 퀸이 있다면 가지치기를 한다.

3. 맨 밑의 행까지 퀸을 위치할 수 있다면 경우의 수를 하나 증가시킨다.

 

이 문제에서 어려운 점은 아래 풀이 코드처럼 최소한의 배열을 사용하고 가지치기를 할 때 반복문을 최소로 사용해야 한다는 데 있습니다.

 

여기서 최소한의 배열을 사용한다는 뜻은, 퀸의 위치를 저장할 때 일차원 리스트만을 이용해서 각 행마다의 위치를 저장한다거나, 가지치기는 현재 행 이전의 행에 대해서만 하고 적절하게 break문을 수행해주는 것 등을 의미합니다.

 

[풀이]

def backTracking(rowPos):
    global answer  
    
    # 퀸을 모두 배치했다면 끝
    if rowPos == n:
        answer += 1
        return
    
    for col in range(n):
        flag = True
        # 이전 행들에 대해서
        for row in range(rowPos):
            # 같은 열에 위치해있거나 대각선에 퀸이 이미 존재한다면 가지치기
            if queenLocation[row] == col or rowPos - row == abs(col - queenLocation[row]):
                flag = False
                break
        if flag:
            queenLocation[rowPos] = col
            backTracking(rowPos + 1)
    
n = int(input())
answer = 0
# 각 row마다 queen이 위치하는 인덱스를 저장하는 리스트
queenLocation = [0] * n
backTracking(0)
print(answer)