[백준/python] 9963번: N-Queen

문제

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

9663번: N-Queen

---

문제 요약

크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 방법의 수를 출력한다.

---

코드

def dfs(i): 
    # i는 현재까지 탐색한 행 인덱스

    global count
    if i == n: # i가 n과 같아지면 모든 퀸을 배치한 경우이다.
        count += 1
        return
    else:
        for j in range(n): # i행의 열들을 검사
            if row[j] or diag1[j + i] or diag2[j - i]: # i, j인덱스의 열, 대각선을 검사하여 퀸이 있으면
                continue # 그 다음 인덱스를 검사

            # 퀸을 놓을수 있는 인덱스 라면
            row[j] = diag1[j+i] = diag2[j-i] = 1 # row, diag들을 모두 체크
            dfs(i+1) # 현재 i에서는 더 이상 나올 수 없으므로 다음 행 탐색
            row[j] = diag1[j+i] = diag2[j-i] = 0 # row, diag들을 모두 체크 해제

n = int(input())

count = 0 # 가능한 해의 개수 저장

# 퀸은 각 행에 하나씩만 존재할 수 있다!!

row = [0 for _ in range(n)]
# 체스판 각 열에 대해 퀸이 배치되었는지를 나타내는 리스트
# row[j] 값이 0이면 해당 열에 퀸이 배치되어 있지 않으므로 (i, j)에 퀸을 배치할 수 있는 상태
# row[j] 값이 1이면 해당 열에 퀸이 배치되어 있으므로 (i, j)에 퀸을 배치할 수 있는 상태

# 퀸은 대각선에 하나씩만 존재할 수 있다!

diag1 = [0 for _ in range(2 * n - 1)]
# 체스판의 왼쪽 아래부터 오른쪽 위까지 올라가는 대각선들을 관리하는 리스트
# 2 * n - 1은 체스판의 왼쪽 아래부터 오른쪽 위까지 올라가는 대각선 방향의 개수
# diag1[j+i] 값이 0이면 (i, j) 인덱스에 퀸을 배치할 수 있는 상태, 1이면 이미 해당 대각선에 퀸이 배치 되어 있는 상태

diag2 = [0 for _ in range(2 * n - 1)]
# 체스판의 왼쪽 위부터 오른쪽 아래까지 내려가는 대각선들을 관리하는 리스트
# 2 * n - 1은 체스판의 왼쪽 위부터 오른쪽 아래까지 내려가는 대각선 방향의 개수
# diag2[j-i] 값이 0이면 (i, j) 인덱스에 퀸을 배치할 수 있는 상태, 1이면 이미 해당 대각선에 퀸이 배치 되어 있는 상태

dfs(0) # i인덱스에 0을 전달

print(count)

---

코드 설명

1. n × n 체스판을 위해 n을 입력받는다.

 

2. (i, j)의 각 열, 대각선에 퀸이 있는지를 체크하는 리스트 row, diag1, diag2를 설정한다.

 

3. dfs함수는 행(i값)을 1씩 증가시키며 퀸을 배치할 수 있는지 i행의 요소들을 검사하는 재귀함수이다.

 

4. diag1은 체스판의 왼쪽 아래부터 오른쪽 위까지 올라가는 대각선들을 관리하는 리스트이다.

 

4-1. diag1[j+i] 값이 0이면 (i, j) 인덱스에 퀸을 배치할 수 있는 상태, 1이면 이미 해당 대각선에 퀸이 배치 되어 있는 상태이다.

 

5. diag2은 체스판의 왼쪽 위부터 오른쪽 아래까지 내려가는 대각선들을 관리하는 리스트이다.

 

5-1. diag2[j-i] 값이 0이면 (i, j) 인덱스에 퀸을 배치할 수 있는 상태, 1이면 이미 해당 대각선에 퀸이 배치 되어 있는 상태이다.

+ j-i가 음수라도 거꾸로 인덱스를 접근할 수 있다.

---

이 문제의 대부분의 코드들은 python 3로 백준에 제출했을 때, 시간 초과 문제가 발생하기 때문에 pypy 3로 제출한다.

그러나 이 코드는 python 3로 제출해도 시간 초과 문제가 발생하지 않는다.

 

pypy3는 자주 쓰이는 코드를 캐싱하는 기능이 있다.

이는 메모리를 조금 더 사용하여 그것들을 저장하므로 실행속도를 개선할 수 있다.

 

즉, 간단한 코드에서는 python 3가 메모리, 속도 측면에서 우세하고,

복잡한 코드(반복된 코드)에서는 pypy3가 우세하다.

 

따라서 코드 상황에 맞게 적절히 사용하는 것이 좋다.

---

n = int(input())

ans = 0
row = [0] * n # 체스판의 x번째 행

def is_promising(x): 
    # x는 현재 검사하려는 행의 인덱스
    for i in range(x): # x 이전 행들을 순회
        if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i):
            # x행에 '놓을 퀸' 위치와 이전 행 i에 '놓인 퀸' 위치의 열이 같으면 같으면 놓을 수 없음.
            # abs(row[x] - row[i])는 가로 거리, x - i는 세로 거리. 같으면 대각선 => 놓을 수 없음.
            return False
    return True

def n_queens(x):
    global ans
    if x == n:
        ans += 1
        return
    else:
        for i in range(n):
            # [x, i]에 퀸을 놓겠다.
            row[x] = i
            if is_promising(x): # 퀸을 주어진 위치 'x'에 놓는 것이 유효하면
                n_queens(x+1) # 그 다음 행으로 

n_queens(0)
print(ans)

위 코드는 가로 거리, 세로거리를 확인하여 이전 행들의 퀸 중 대각선에 있는 퀸이 존재하는지를 확인하는 코드이다.

유의할 점은 python 3로 제출하면 시간 초과 문제가 발생하므로 pypy3로 제출하면 된다.