- Problem Link : https://www.acmicpc.net/problem/9663
문제
- N x N 체스판 위에 N 개의 퀸을 서로 공격할 수 없게 놓는다.
입력
- 첫째 줄, N이 주어진다.
출력
- 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
풀이
이전에 풀었던 암호 만들기 문제를 풀고 난 후 백트래킹 개념에 대해서 더 자세히 알아보고 이해하기 위해 백트래킹으로 유명한 문제인 해당 문제를 풀어보았다.
당연하게도 백트래킹 기법을 이용해서 문제를 해결한다.
0. 첫번째 행부터 시작한다.
1. 첫번째 열부터 퀸을 놓으면서 진행한다.
2. 퀸을 놓으면 해당 체스판의 상태가 유망한지(promising) 판단한다.
3. 만약 유망하다면 다음 행으로 이동해서 퀸을 놓기 시작한다.
4. 만약 유망하지 않다면 더 이상 퀸을 놓지 않고 돌아간다.BackTrackin Algorithm?
유망하지 않을 경우 퀸을 더 이상 놓지 않고 돌아가는 이러한 방법을 백트래킹이라고 한다.
DFS(또는 BFS)으로 모든 Node를 검색한 뒤의 유망성을 점검하여 유망하지 않으면 돌아간 후 다른 분기(branch)를 탐색하는 방식이다.
더 자세한 내용은 백트래킹에 대해 설명한 문서를 확인할 수 있다.
- 이 때 유망한지(promising) 판단은 어떻게 할까?.
- 퀸은 가로, 세로, 대각선 위치에 다른 퀸이 있을시 위치할 수 없다
- 따라서 퀸을 배치한 후 해당 열과 같은 열에 놓인 퀸이 있는지, 대각선에 위치한 퀸이 있는지 확인하여 False 또는 True를 리턴
- 행을 확인하지 않는 이유는 퀸을 놓고 유망하다고 판단되면 다음 행으로 넘어가기 때문에 행별로 퀸은 하나밖에 위치할 수 없다.
유망성 검사
def promising(x):
for i in range(x):
if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i):
return False
return True- 다음과 같이 유망성을 검사한다.
- 위에서 서술했듯이 행 별로 퀸을 하나 배치시키면 바로 다음 행으로 이동해 퀸 배치를 진행하기 때문에 한 행에 또다른 퀸이 배치됐는지 확인할 필요가 없다.
- 따라서 row 리스트에 들어있는 열의 위치를 비교해서 같은 열에 퀸이 배치돼있는지 확인하고 행의 차이가 열의 차이와 같은지(대각선에 위치했는지)를 확인하여 유망성을 판단한다.
BackTracking
def nqueen(x):
global ans
if x == n:
ans += 1
return
for i in range(n):
if visited[i]:
continue
row[x] = i # [x, i]에 퀸을 위치
if promising(x):
visited[i] = True # i열 퀸 배치 표시
nqueen(x + 1) # i열에 퀸을 배치시킨 후 다음 열로 이동
visited[i] = False # i열 퀸 배치 해제- 다음과 같이 BackTracking을 구현했다.
- x가 n과 같다면 모든 행에 퀸을 놓았다는 것을 의미하고 문제에서 요구하는 경우에 해당하므로 경우의 수를 +1 해주고 return 시킨다.
- 만약 방문한 적이 없는 열이라면 해당 열에는 퀸을 위치시킬 수 있다는 것을 의미하므로 해당 위치에 퀸을 배치시킨 후 유망성을 검사한다.
- 유망성이 있다면, 해당 열에 퀸을 배치했다고 표시한 후 다음 행으로 건너가 퀸 배치를 진행한다.
- 유망성이 없다면, 해당 위치에 퀸을 배치 시킬 수 없으므로 추가적인 퀸 배치를 진행하지 않는다.
결국 BackTracking 기법은 DFS, BFS와 같이 모든 경우의 수를 방문하는 탐색 방법에서 중간에 해당 조건을 비교할 수만 있다면 조건을 비교하면서 탐색을 진행하여 유망성이 없는지를 모든 탐색 돌기 전에 판단해 유망성이 없는 경우를 배제시키면서 탐색을 하는 방식이다.
당연하게도 단순히 모든 노드를 방문하며 탐색하는 DFS, BFS보다 유망성이 없는 경우의 수를 배제시키는 백트래킹(BackTracking) 알고리즘을 사용한 방식이 더 빠르게 실행 가능하다.
오류 및 해결
코드를 작성후 python3로 제출했으나 시간 초과가 발생했다. visited를 추가해 실행 시간을 단축시켰음에도 시간 초과가 발생해서 구글링해보니 python이 백트래킹 알고리즘을 사용하기에 부적합한 언어이며 pypy3로 제출해야한다는 것을 알 수 있었다. pypy3로 제출하니 정상적을 실행이 완료되었음을 알 수 있다.
코드
import sys
def promising(x):
for i in range(x):
if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i):
return False
return True
def nqueen(x):
global ans
if x == n:
ans += 1
return
for i in range(n):
if visited[i]:
continue
row[x] = i # [x, i]에 퀸을 위치
if promising(x):
visited[i] = True # i열 퀸 배치 표시
nqueen(x + 1) # i열에 퀸을 배치시킨 후 다음 열로 이동
visited[i] = False # i열 퀸 배치 해제
n = int(sys.stdin.readline())
ans = 0
row = [0] * n
visited = [False] * n
nqueen(0)
print(ans)
Be Honest, Be Harder, Be Stronger