반응형
이 문제는 정말 유명한 N-Queen 문제이다.
퀸은 양옆, 위아래, 대각선 방향 어디든 갈 수 있다.
따라서 한 행에 최대 하나의 퀸이 존재할 수 있다.
이때 N*N 크기의 체스판 위에서 N개의 퀸이 서로 공격할 수 없도록 배치하는 경우의 수를 구하는 문제이다.
만약 N = 8 이라면 위의 그림과 같이 배치할 수 있을 것이다.
N-Queen 문제는 dfs, 백트래킹을 필요로 한다.
먼저 dfs를 위해 체스판을 표현할 배열이 필요하다.
퀸이 서로 공격할 수 없게 배치하려면 무조건 한 행에는 최대 한 개의 퀸만 존재할 수 있다.
그래서 a_row라는 배열을 만들었는데, 이 배열은 특정 행의 어느 열에 퀸이 위치하는지를 저장한다.
예를 들어 위 그림처럼 1행에서 6열에 퀸이 위치한다면
a_row[1] = 6 일 것이다.
그 후 이 배열을 사용해서 1행부터 N행까지 dfs를 하면 되는데, 이때 백트래킹 과정을 통해 가능성이 없는 경우에는 dfs를 더이상 수행하지 않는다.
1. 같은 열에 퀸이 이미 존재하는 경우
-> a_row 배열 사용 : 만약 a_row[i] 값이 0이 아니라면 i 열에 퀸이 존재하는 것.
2. 대각선 방향에 퀸이 이미 존재하는 경우
-> 이전 행에 존재하는 퀸과의 가로, 세로 거리 비교 : 만약 가로, 세로 거리가 같다면 대각선 방향에 퀸이 존재.
이 두 가지 경우를 가지고 백트래킹을 하면 수행시간을 훨씬 단축할 수 있다.
예시 코드
import sys
N = int(sys.stdin.readline())
# 가능한 경우의 수
result = 0
a_row = [0]*(N+1)
def DFS(row, N):
global a_row
if(row > N):
global result
result += 1
else:
for i in range(N):
a_row[row] = i+1
if(isOkay(row, i+1)):
DFS(row+1, N)
else:
a_row[row] = 0
# 백트래킹 과정
def isOkay(row, col):
global a_row
for i in range(1, row):
# 위
if(a_row[i] == col):
return False
# 대각선
if(abs(a_row[row]-a_row[i]) == abs(row-i)):
return False
return True
# dfs 수행
DFS(1, N)
print(result)
반응형
댓글