미소를뿌리는감자의 코딩
[백준 2024/04/03] 9663번 N-Queen 본문
https://www.acmicpc.net/problem/9663
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)
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/09/07] 1978번 소수 찾기 (0) | 2024.09.07 |
---|---|
[백준 2024/04/16] 2110번 공유기 설치 (0) | 2024.04.16 |
[백준 2024/04/04] 7576번 토마토 (0) | 2024.04.05 |
[백준 2024/04/05] 1012번 유기농 배추 (0) | 2024.04.05 |
[백준 2024/03/29] 15650번 N과 M (2) (0) | 2024.03.29 |