[Python/파이썬] 백준 9663번 - N-Queen

문제 설명

9663번: N-Queen

---

풀이 코드

이 문제는 가능한 모든 경로를 탐색하되, 조건을 만족하지 않는 경로는 중간에 가지치기하여 더 이상 탐색하지 않는 백트래킹 알고리즘을 사용하여 풀 수 있었다.

 

문제에 대해 설명하자면, 체스에서 퀸은 상하좌우 대각선 모든 방향으로 원하는 만큼 이동할 수 있다.

그렇기 때문에 퀸을 서로 공격할 수 없도록 놓기 위해서는 체스판위의 행, 열 마다 하나의 퀸이 존재해야한다.

처음에는 2차원 배열로 푸는 방법이 더 이해가 쉬울것 같아서 2차원 배열로 문제를 풀고 제출해보았지만 pypy3로 제출했음에도 시간초과가 발생했고 코드 가독성 또한 안좋았었다.

 

그래서 알아본 결과 1차원 배열로 문제를 푸는 것이 더 수월해보였다.

1차원 배열로도 문제를 풀 수 있는 이유는 어차피 각 행과 열에는 하나의 퀸만이 존재할 수 있기 때문이다.

 

1차원 배열을 사용했기 때문에 대각선 체크를 어떻게 해야하는지가 난감했는데 다음과 같은 공식으로 대각선을 체크할 수 있었다.

대각선 체크 공식

쉽게 이해할 수 있도록 그림을 그려보았다.

아래의 설명대로 서로 같은 대각선에 있다면 해당 퀸들의 행의 차이와 열의 차이가 같은 것을 볼 수 있다.

이제 아래와 같은 공식으로 대각선을 체크하여 퀸이 서로 공격이 가능한지 않한지를 체크하여 문제를 풀어보자.

이 외의 설명에 대한 부분은 주석으로 충분하다고 생각한다.

 

 

정답 코드 (PyPy3로 제출)

import sys
input = sys.stdin.readline

n = int(input())

# 퀸이 공격을 받는지 확인
def attack(x):
    for i in range(x): 
        # 같은 행에 퀸이있거나 대각선에 퀸이 있는 경우
        if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i):
            return True
    return False

def dfs(start):
    global cnt

    if start == n: # 마지막까지 탐색했을 경우
        cnt += 1
    else:
        for i in range(n):
            row[start] = i
            if not attack(start): # 퀸의 위협을 받지 않는다면 다음 탐색
                dfs(start + 1)

row = [0] * n # row[i]는 i행에 퀸이 있다는 의미
cnt = 0
dfs(0)

print(cnt)