[백준] 9663번 : N-Queen (백트래킹 골드Ⅳ) - Python

문제

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

9663번: N-Queen

문제

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

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

입력

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

출력

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

예제 입력 1

8

예제 출력 1 

92

풀이

접근

내가 퀸을 놓은 위치를 기준으로 다음 퀸을 놓을 자리를 탐색하므로 기본 접근은 DFS이다.

그리고 백트래킹을 이용한다는 것

퀸이 서로를 잡지 못하게 놓으려면 퀸이 하나 놓인 자리의 같은 행(가로), 같은 열(세로), 대각선은 불가하다는 것.

예시) n=4 이고 visited = [1, 3, 0, 2] 인 경우, 체스판을 그려보면 아래와 같다. (1이 퀸)

    0 1 0 0
    0 0 0 1
    1 0 0 0
    0 0 1 0

같은 행 불가 처리

• 이건 visited 리스트에서 처리해주면 된다.
• 해당 리스트의 인덱스를 행, 값은 열을 나타내게 하면 인덱스는 유일하기 때문에 같은 행에는 들어갈 수 없게 처리 가능
• (1, 3)에 놓은 경우, visited[1] = 3 으로 표현
• (1, 3)에 뒀다면 그 뒤로 (1, x)는 모두 불가이기 때문에 인덱스 하나엔 한 값만 들어가게 하면 됨.

DFS

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

    else:
        for col in range(n):
            visited[row] = col
            if check(row): 
                dfs(row + 1)

• dfs(row)은 row번째 행의 어느 열에 퀸을 놓을지를 선택한다.
• for col in range(n) 👉🏻 n-1까지 진행
• visited[row] = col 👉🏻 (row, col) 위치에 퀸을 두었을 때
• if check(row)로 이 위치에 놓는 것이 맞는지 확인한다.
• 올바르다면 재귀탐색 dfs(row + 1) 
• row가 n이 되었다 👉🏻 dfs(n)까지 중간에 끝나지 않았다 👉🏻 모든 퀸이 잘 놓였다.

같은 열, 대각선 불가 처리

def check(now_row):
    for row in range(now_row):
        if visited[now_row] == visited[row] or now_row - row == abs(visited[now_row] - visited[row]):
            return False
    return True

• check 함수로 DFS 내에서 검사
• 다른 열은 리스트에서 했고, 다른 행일 때만 검사하면 되므로 퀸을 놓은 행(now_row)이 올바른지 검사한다.
• now_row 행의 퀸 위치와, 0번째 행부터 n-1번째 행까지 놓여진 퀸의 위치를 비교한다.
• 방금 놓은 now_row 퀸은 (now_row, visited[now_row]) 에 놓여져있다.
• 같은 행 - 검사 x
  • 각 행(인덱스)당 하나를 놓으므로
• 같은 열- 검사
  • visited[now_row] == visited[row]
• 대각선 - 검사
  • 만약 대각선에 놓여있다면 가로 거리와 세로 거리가 같을 것임
  • now_row - row == abs(visited[now_row] - visited[row])
• now_row 행에 놓여진 퀸이 규칙을 만족하지 못했다면 False 를 반환한다.

전체 풀이 코드

import sys
input = sys.stdin.readline

n = int(input())
	
visited = [-1] * n
cnt = 0

def check(now_row):
    for row in range(now_row):
        if visited[now_row] == visited[row] or now_row - row == abs(visited[now_row] - visited[row]):
            return False
    return True

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

    else:
        for col in range(n):
            visited[row] = col
            if check(row): 
                dfs(row + 1) 
                
dfs(0)
print(cnt)