[baekjoon] 백준 9663번(파이썬): N-Queen

문제

9663번: N-Queen

알고리즘

- 체스 판에서 퀸이 움직일 수 있는 방향을 생각하면 하나의 열의 하나의 퀸만을 놓을 수 있다.

- 따라서 n개의 열의 퀸을 다 놓을 수 있는지 확인한다.

- 이때, 대각선으로 퀸은 이동할 수 있으므로 대각선의 퀸을 놓을 수 있는지 확인해준다.

- 백 트래킹을 통해 퀸을 n개 놓을 수 없다면 다른 경우의 수로 문제를 해결할 수 있게 한다. 

코드

import sys
# pypy3 해결.. python(3%) 시간초과


# 대각선의 퀸이 있는지 확인
def check(x):
    for i in range(x):
        if abs(graph[x] - graph[i]) == x - i:
            return False
    return True


# 체스 판의 열을 dfs 탐색
def dfs(queen):
    global res

    # n번째 퀸을 놓으려 한다면 리턴 (n개의 퀸을 놓았기 때문.)
    if queen == n:
        res += 1 # 방법의 수 카운트
        return

    # 모든 체스판의 열을 확인
    for i in range(n):
        # i 번째 열의 퀸을 놓지 않았다면
        if not visited[i]:
            graph[queen] = i # (queen, i)에 퀸을 둔다.

            # 대각선의 겹치는 퀸이 있는지 확인
            if check(queen):
                # 백 트래킹
                visited[i] = True # 퀸을 놓는다.
                dfs(queen + 1) # 재귀적으로 퀸을 놓을 수 있는 열을 찾는다.
                visited[i] = False # 재귀 탐색 후 퀸을 n개 놓을 수 없다면 퀸을 놓지 않는 것으로 초기화 후 다른 열을 탐색


n = int(sys.stdin.readline())
graph = [0 for _ in range(n)] # n번째 열의 퀸의 위치
visited = [False for _ in range(n)] # 체스판의 탐색 여부
res = 0 # 퀸을 놓는 방법의 수

dfs(0)
print(res)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법