[백준/Python] 9663 N-Queen
1. 문제 설명
N-Queen 문제는 크기가 N x N 인 체스판 위에 퀸을 배치하는 문제이다. 퀸은 체스에서 가장 강력한 말로, 수직, 수평, 대각선 방향으로 움직일 수 있다. 이 문제는 퀸 N 개를 N x N 크기의 체스판에 배치하되, 어떤 두 퀸도 서로를 공격할 수 없는 방식으로 배치하는 것이다.
즉, 어떤 퀸도 같은 행, 열, 대각선 위에 있으면 안된다.
2. 문제 접근 방법
- 각 행에는 하나의 퀸만
체스판의 각 행에는 오직 하나의 퀸만 배치할 수 있다.
- 백트래킹 기법
모든 가능한 위치에 퀸을 배치하고, 조건에 맞지 않은 위치는 조기에 배제한다. 이를 위해서 재귀 함수를 사용한다.
- 유망성(promising) 검사
현재 위치에 퀸을 놓았을 때, 이전에 배치된 퀸들과 충돌하지 않는지 검사한다.
3. 코드 및 설명
def is_promising(row):
for before_row in range(row):
# 같은 열이나 대각선에 위치하는 경우 체크
if (graph_col[before_row] == graph_col[row] or
abs(graph_col[before_row] - graph_col[row]) == abs(before_row - row)):
return False
return True
def dfs(row):
global result
if row == n:
result += 1
return
for i in range(n):
graph_col[row] = i # 현재 행에 퀸을 놓음
if is_promising(row): # 유망성 검사
dfs(row + 1) # 다음 행으로 이동
n = int(input()) # 체스판의 크기 N 입력
graph_col = [0] * n # 각 행의 퀸 위치를 저장하는 배열
result = 0 # 경우의 수를 저장할 변수
dfs(0) # 첫 번째 행부터 시작
print(result) # 결과 출력코드 설명
is_promising 함수
현재 행에 퀸을 놓았을 때, 이전 행의 퀸들과 충돌하는지 확인한다. 같은 열이나 대각선 상에 있는 경우 False를 반환한다.
- 같은 열 체크
함수는 현재 행 row 에 대하여 이전의 모든 행 before_row 를 순회한다. graph_col[before_row] == graph_col[row] 이 조건은 현재 행의 퀸과 이전 행의 퀸이 같은 열에 있는 지 검사한다. 만약 같은 열에 있다면 이 위치는 조건에 해당하지 않아 False 를 반환한다.
- 대각선 체크
abs(graph_col[before_row] - graph_col[row]) == abs(before_row - row) 이 조건은 대각선상에 있는지를 검사한다. graph_col[before_row] - graph_col[row]는 열의 차이를, before_row - row는 행의 차이를 나타낸다. 체스판에서 대각선상의 위치는 행과 열의 차이가 동일하다. 따라서 이 조건이 만족하면 현재 퀸은 이전 퀸가 대각선상에 위치하게 되므로 False 를 반환한다.
위 두 조건 중 어느 것도 만족하지 않으면, 현재 위치는 유망한 위치로 간주되며 True 를 반환한다.
dfs 함수
깊이 우선 탐색을 사용해 재귀적으로 문제를 해결한다. 모든 행에 대해 유망한 위치에 퀸을 놓고, 마지막 행까지 도달하면 경우의 수를 하나 증가시킨다.
변수 graph_col
각 행에 배치된 퀸의 열 위치를 저장한다. 예를 들어 graph_col[0] = 3은 첫 번째 행의 퀸이 네 번째 열에 있다는 것을 의미한다.
위 코드의 제출 결과 시간 초과라는 결과를 얻게 되었다.
pypy 3로 제출하여 문제를 맞출 수 있었다.
