[Python] Baekjoon9663: N-Queen

N-Queen

10 초

128 MB

56575

28380

18609

49.681%

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

풀이

원리나 풀이 부분은 이미 충분히 다뤄왔기 때문에 상세히 다루지는 않겠습니다..

백트래킹(Backtracking)의 개념과 DFS로의 확장, N-Queen

 

답안 기록: 인덱스가 곧 행, 그 안의 숫자는 열

정답 저장은 어떤 방식으로 해야하지 생각하면 복잡할 수 있습니다.

백트래킹의 대부분의 문제의 경우 인덱싱을 활용해 정답을 저장하는 것이 좋습니다. 

answer = [0 for i in range(N)] # N 크기의 배열 준비

바로 위 링크의 그림을 참조해서 답안으로 나타내면 다음과 같습니다.

[2,4,1,3] # 4x4 일 때 유일한 N-Queen의 답안

즉, [ 1행일 때 2 → 2행일 때 4 → 3행일 때 1 → 4행일 때 3 ] 로 진행해 답을 찾은 경우입니다.

 

답을 구할 때의 모습?

백트래킹에서 사용하는 재귀메소드에 의해서 재귀의 깊이는 0에서 출발해 N까지 도달할 수 있습니다.

N에 도달하면 정답이지만 그 전에 퀸을 두지 못해 더 이상 진행하지 못하는 경우 돌아가서 다른 답을 찾아야 합니다.

둘 수 있는지, 둘 수 없는지는 메소드나 여러 조건들을 통해 알려줘야합니다.

def dfs(depth):
    global cnt
    if depth == N:
        cnt += 1
        return
        
    # 진행 중인 경우
    for i in range(N):
    	# 깊이가 0일 때는 어디든 가능 or 방문한 적 없고 대각 공격방향이 아닐 때
    	if depth == 0 or (not visited[i] and isPossible(depth, i)):
            visited[i] = True # 방문 체크
            answer[depth] = i # 둔 곳 기록
            dfs(depth + 1)   # 다음 행 탐색
            visited[i] = False # 방문 해제

 

N-Queen의 백트래킹

첫번째 퀸은 어디든지 둘 수 있습니다. 그 다음 퀸부터 문제죠.

현재 퀸을 이전 퀸들의 공격권에 있는 자리에 둘 수 없습니다.

 

공격 방향

퀸의 공격은 같은 행, 같은 열, 대각입니다.

→ 같은 행은 검사해줄 필요가 없습니다. 어차피 퀸을 두고 다음 행으로 바로 이동하기 때문이죠.

→ 같은 열은 이전 퀸들의 열 위치를 확인해주어야 하는데 이것도 크게 검사할 필요가 없습니다. 왜냐면 방문 체크 배열에 이미 몇 번째 열에 퀸을 둘 것인지 체크했기 때문입니다.

→ 대각이 제일 문제죠. 하지만 A를 어떤 대각 방향으로 움직일 때는 생각하면 간단합니다.

대각 = [오른쪽이나 왼쪽 n 칸 이동] + [위 쪽이나 아래쪽 n칸 이동]

다시 말해 체스판 위에서 서로 다른 A, B의 행과 열을 각각 빼주고 비교해 절대값이 같다면 대각이라는 결론이 나옵니다.

def isPossible(depth, col):
    judge = True
    for i in range(depth):
        if abs(depth - i) == abs(answer[i] - col): # 이전 행들의 퀸과 대각선으로 겹치면 False
            judge = False
            break
    return judge

 

전체 코드

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

    for i in range(N):  # 깊이가 0일 때는 어디든 가능
        if depth == 0 or (not visited[i] and isPossible(depth, i)):
            visited[i] = True
            answer[depth] = i
            dfs(depth + 1)
            visited[i] = False


def isPossible(depth, col):
    judge = True
    for i in range(depth):
        if abs(depth - i) == abs(answer[i] - col):
            judge = False
            break
    return judge

N = int(input())
cnt = 0 # n-Queen의 개수
answer = [0 for i in range(N)] # N 크기의 배열 준비
visited = [False for i in range(N)] # 방문 체크 배열

dfs(0)

print(cnt)