[백준 2024/04/03] 9663번 N-Queen

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

9663번: N-Queen

 

1. 접근 방법

https://www.youtube.com/watch?v=1Bh6DBcKgOc

이 영상 덕분에 좋은 풀이를 잘 이해할 수 있었다.

 

동일한 대각선 위에 있는지 확인하는 방법을 알게 되었다.

[x+y] 가 동일한지, [x-y] 가 동일한지 확인하면 된다.

그림으로  설명하는게 편할 것 같아서 그림을 그려보았다.

 

 

우선 같은 세로 줄에 위치하는지 확인하기 위해서는 v1이라는 선언된 리스트를 통해서 확인이 가능하다.

처음에는 0을 채워놓고, 해당 값이 queen을 놓았을 때는 1을 채워놓는다.

이후 차후에 또 해당 위치에 접근하게 된다면, 같은 세로 줄에 queen이 위치하게 되므로 더 이상 다음 단계로 넘어가지 못한다.

 

v2와 같은 경우에는 오른쪽 위에서 왼쪽 아래로 향하는 대각선이다. 이 대각선의 특징은 x + y 가 같은 값이라는 점이다.

따라서 이도 위와 같은 방식으로 비교해서 코드를 진행한다. 

 

왼쪽 위에서 오른쪽 아래로 향하는 대각선의 경우는 x-y의 값이 동일한 것을 확인할 수 있으며, 이 이외는 위와 동일하다.

 

코드 일부를 보면서 더 이해해보자.

def dfs(n):
    global cnt
    if n == N:
        cnt += 1
        return

    for j in range(N):
        if v1[j] == v2[n + j] == v3[n - j] == 0:
            v1[j] = v2[n + j] = v3[n - j] = 1
            dfs(n + 1)
            v1[j] = v2[n + j] = v3[n - j] = 0

 

이렇게 구성되는데, 

n의 경우 가로 줄을 의미한다. 특정 위치에 겹치는 queen이 없어서, 해당 위치에 queen을 놓게 되면, 

v1[j] = v2[n+j] = v3[n-j] = 1로 체크해 준다.

이후 dfs(n+1)을 통해서 다음 가로 줄로 넘어가서 또 계산을 진행해 준다.

또 다음 for 문의 j 값은 queen이 놓아지지 않은 상태에서 계산을 진행하야하는 다른 case이므로, 

v1[j] ... = 0으로 다시 바꾸어주고 계산을 진행한다.

 

2. 코드

def dfs(n):
    global cnt
    if n == N:
        cnt += 1
        return

    for j in range(N):
        if v1[j] == v2[n + j] == v3[n - j] == 0:
            v1[j] = v2[n + j] = v3[n - j] = 1
            dfs(n + 1)
            v1[j] = v2[n + j] = v3[n - j] = 0


N = int(input())
cnt = 0
v1 = [0] * N
v2 = [0] * (2 * N)
v3 = [0] * (2 * N)
dfs(0)

print(cnt)