[Python/Baekjoon] 9663. NQueen

💬 문제

문제 난이도: 백준 골드 4

문제 링크: https://www.acmicpc.net/problem/9663

❗️접근 방법

1. 재귀를 활용해 가능한 경로의 수를 알아낸다.
2. 더이상 사용할 수 없는 행과 열, 그리고 대각선의 고유 번호를 저장한다. (v_col, v_dia1, v_dia2)
3. 시간을 줄이기 위해 N이 짝수일 때에 0번째 행에 대해 N//2개의 열에 해당하는 가능한 경로만 탐색하고, 마지막에 *2해주면 된다. (대칭이기 때문에)

✅ 정답 코드

import sys
input = sys.stdin.readline

N = int(input())
# 현재 행에서 놓을 수 있는 col이 어디인지
# -> 이미 사용한 col이 무엇인지 알려주는 역할
v_col = [0 for _ in range(N)]
# 둘 수 없는 대각선1 정보
v_dia1 = [0 for _ in range((N)*2)]
# 둘 수 없는 대각선2 정보
v_dia2 = [0 for _ in range((N)*2)]

cnt = 0
def solution(depth, flag):
    global cnt 

    if depth == N:
        cnt += 1
        return

    if flag == True: # N이 짝수일 때 0번째 row에서
        for i in range(N//2):
            if v_col[i] == 0 and v_dia1[(depth - i +N)] == 0  and v_dia2[(depth + i )] == 0:
                v_col[i] = 1
                v_dia1[depth-i+N] = 1
                v_dia2[depth+i] = 1

                solution(depth+1, False)

                v_col[i] = 0
                v_dia1[depth-i+N] = 0
                v_dia2[depth+i] = 0

    else:
        for i in range(N):
            # 퀸을 둘 수 있는 곳인지 
            if v_col[i] == 0 and v_dia1[(depth - i +N)] == 0  and v_dia2[(depth + i )] == 0:
                v_col[i] = 1
                v_dia1[depth-i+N] = 1
                v_dia2[depth+i] = 1

                solution(depth+1, False)

                v_col[i] = 0
                v_dia1[depth-i+N] = 0
                v_dia2[depth+i] = 0
        
if N % 2 == 0:
    solution(0, True)
    print(cnt*2)
else:
    solution(0, False)
    print(cnt)

✍️ 미처 알지 못했던 부분

• N이 짝수일 때 0번째 행에서는 전체 열의 반만 탐색해도 된다는 것.
• col과 row에 대한 방문 기록뿐만 아니라 대각선에 대한 방문 기록도 남길 수 있는 방법이 있고, 남겨야 나머지 코드가 간결하고 시간초과도 나지 않는다는 것.