문제

링크

풀이

처음 이 문제를 풀 때 2차원 배열을 생성하였다. 모든 (x,y)를 탐색하면서 해당 좌표에 퀸을 놓을 수 있다면 해당 좌표의 가로, 세로, 대각선 지점에 방문표시를 한다. 이렇게 모든 좌표들에 대해 퀸을 놓을 수 있는지 확인한 후 답을 구하도록 하는 재귀적인 방법을 사용했다. 하지만, 답은 0이 나왔고, 디버깅을 해보니 좌표의 대각선의 방문을 확인하는 코드에 문제가 있었다. (코드의 양이 좀 많았는데 오류가 나니 멘탈이 나갔다...) 코드를 수정하는데에 하루를 쏟았으나 이상한 답이 나왔다. 이후 다른사람의 풀이를 참고하여 풀었다.

풀이 방법은 위의 배열을 이용하여 풀면 된다. 아래 코드에서 depth는 행이며 col은 열을 의미한다. 위에서부터 0행, 1행, ... 순서대로 진행하면서 퀸을 배치할 열을 정하는 것이다. 간단하게 말하자면 depth=0일 때 (0(depth),0(col))에 퀸을 놓는다. 퀸을 배치했으면 바로 다음 행(depth=1)으로 넘어가 탐색한다. 처음 col=0이므로 (1,0)에 퀸을 놓으려 할 것이다. 하지만 (0,0)에 있는 퀸의 이동범위 때문에 (1,0)에 퀸을 놓지 못한다는 것을 a, b, c 배열을 통해 알 수 있다. 다음인 (1,1)의 경우도 같다. 그래서 (1,2)에 퀸이 놓아진다.

이러한 방식으로 퀸이 놓을 수 있는 경우에만 그 다음으로의 탐색을 진행하고, 답이 아니라면 전 단계로 돌아가 답을 찾도록 한다. 이는 아래의 그림과 같다.

코드

import sys

input = sys.stdin.readline
N = int(input())
a, b, c = [0] * N, [0] * (2 * N - 1), [0] * (2 * N - 1)
result = 0


# depth는 행
def dfs(depth):
    global result
    if depth == N:
        result += 1
        return
    # col는 열
    for col in range(N):
        # a,b,c 배열을 이용해 서로의 퀸이 공격할 수 없는 위치를 정한다.
        if not a[col] and not b[depth + col] and not c[depth - col + N - 1]:
            a[col] = b[depth + col] = c[depth - col + N - 1] = 1
            dfs(depth + 1)  # 다음 행으로 탐색 진행
            a[col] = b[depth + col] = c[depth - col + N - 1] = 0


dfs(0)
print(result)

참고 : https://geonlee.tistory.com/40
https://rebas.kr/761
https://velog.io/@qweadzs/BOJ-9663-N-QueenPython