[백준] 재귀, 백트래킹 <3>
#9663 N-Queens
9663번: N-Queen
백트래킹 문제에서 널리 알려진 N Queens 문제이다. 간단하게 설명하자면, N x N 크기의 체스판에서 N개의 퀸들이 서로 공격할 수 없는 위치의 경우의 수를 세는 문제이다.
1. 백 트래킹이란?
N Queens 문제를 들어가기 전에 백트래킹이 어떤 알고리즘인지 생각해보자.
해당 문제를 풀 수 있는 방법 중 하나는 모든 경우의 수를 다 생각해 보는 것이다. N x N 의 체스판 위에 N개의 체스말들을 모두 올려놓을 수 있는 경우의 수를 생각해본다.
첫번째 퀸은 N^2 개의 위치에 올라갈 수 있고, 두번째는 N^2 - 1, 세번째는 N^-2… N번째는 N^2 - N-1. 모든 경우의 수는 그것들을 다 곱하는 방식이다. 보면 알겠지만 N이 커질수록 어마어마한 연산량이 된다.
이때 백 트래킹을 사용한다면 경우의 수를 줄일 수 있다.
백 트래킹이란 경우의 수를 생각해 진행하지만, 진행 중 가능성이 없는 경우엔 뒤로 되돌아가 다시 세는 방식이다.
2. 백 트래킹의 필수요소
즉 백트래킹 연산에서 필요한 것들은 다음과 같다
- 종료조건
- 종료조건이 아닐 시 조건에 따라 하위 재귀로 진입.
- 유망조건(선택적으로 가지치기)
백 트래킹에서 말하는 유망조건이란, 문제의 조건에 따라 해당 경우의 수가 불가능하다고 판단되면 아래 가지들을 모두 잘라내는 것이다.
예를 들어 8 x 8의 체스판에서 1,1 에 퀸을 두었다. 다음번 퀸을 1,2에 두는 경우의 수는 문제 조건에 따라 불가능하다. 즉 1,2부터 시작하는 하위 경우의 수를 시도하지 않는 것이다.
이런 조건을 따르면 많은 경우의 수들을 생략할 수 있을 것이다.
3. N Queens 문제에서의 적용
다시 N-Queens 문제로 돌아와 필수요소들을 하나씩 생각해보자
- 종료조건 → 해당 경우의 수가 유망하면서 동시에 N개의 퀸을 모두 두어야 한다.
종료조건이 아닐 시 하위가지 진입방법 → 첫번째 행부터 차례대로 퀸을 둔다. (1번행 → 2번행 → 3번행 → 4번행 …).
이때 하위가지 진입 조건이 유망조건과 충돌하면 안된다.
- 유망조건 → 퀸이 이전에 두었던 퀸의 공격방향에 놓여있지 않는다. 즉 같은 열이나 대각선에 두지 않는다.
4. 코드
참고: 파이썬으로 작성시 아마 맞는 로직으로 작성했어도 시간초과가 나오는 듯 하다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import sys
## n = depth
# 기본 전제 : 같은 행에는 두지 않는다.
answer = 0
def nQueens(i, col):
global answer
n = len(col) - 1
if (promising(i, col)):
if (i == n): # 끝까지 다 탐색한 경우
answer += 1
else:
for j in range(1, n + 1):
col[i + 1] = j
nQueens(i+1, col)
def promising(i, col): # 유망조건
k = 1
flag = True
while (k < i and flag):
if (col[i] == col[k] or abs(col[i] - col[k]) == (i - k)): # 첫번째 조건: 같은열, 두번째 조건: 대각선
flag = False # 위 조건을 만족하면 거짓
k += 1
return flag # 모든 조건을 피해가면 참
## 같은 열 두지 않음
## 대각선에 두지 않음.
N = int(sys.stdin.readline().strip())
col = [0] * (N + 1) # 초기 열
nQueens(0,col)
print(answer)
코드 설명 (N = 4인 경우)
N = 4 인 경우, 입력하는 초기 행은 col = [0,0,0,0,0] 이다. 이때 각 요소는 각 인덱스인 행에서의 퀸의 위치이다. 그렇기 때문에 0번 인덱스의 0은 로직에 따라 첫번째 체스말을 어디든 둘 수 있게 해주는 더미 값이다.
예를 들어 [0,1,2,3,4] 의 경우 퀸의 위치는 (1,1) , (2,2) , (3,3) , (4,4) 가 된다.
i = 0 인 경우 ⭕
최초의 nQueens 함수에 0, [0,0,0,0,0]을 입력하게 되면 i = 0이다. 처음 만나는 promising은 1 < 0을 만족하지 못해 True를 반환한다. 이때 n = 4로 고정이므로 else로 넘어가 for j문을 돌아준다.
for j 반복문이 1부터 시작하는 이유는 앞에서 설명한 col list의 0번 인덱스가 더미값인 이유와 같다. 실제로 그 곳에 두지 않기 때문이다.
col[i+1] = j 에서 col[1] = 1 이 된다. 이 뜻인 우리가 (1,1)의 자리에 퀸을 위치시켰다는 의미다. 이제 새로운 i = 1, [0,1,0,0,0]을 가지고 다음 nQueens함수 재귀를 시작한다.
i = 1 인 경우 ⭕
이때도 역시 1 < 1을 만족하지 못하기 때문에 promising은 True를 반환한다. for j 반복문으로 바로 넘어가 col[2] = 1를 시험해본다.
i = 2인 경우 - 1 ❌
i = 2, col = [0,1,1,0,0]
이제 promising의 1 < 2 조건이 만족됐으므로 안쪽 조건문을 살펴본다. 조건문 앞쪽의 col[i] = col[2] = 1, col[k] = col[1] = 1 을 만족했다. 이 조건은 퀸을 같은 열에 위치하지 못하게 하는 것이다. 이 조건문을 만족했기에 promising은 False를 반환한다.
이때 이 조건을 만족시키지 못했으므로 [0,1,1,0,0]의 이후 조건들은 전부 탈락시킨다. 이제 아래 재귀가 일어나지 않기 때문에 i = 1인 경우의 for j 반복문으로 돌아오게 되어 col[2] = 2를 시험한다.
i = 2인 경우 - 2 ❌
i = 2, col = [0,1,2,0,0]
바로 promising을 살펴보자. 조건문 앞쪽 같은 열 조건은 피했다. col[i] = 2, col[k] = 1 이다. 조건문 뒷쪽은 대각선의 조건을 살펴보는 것이다. 이때 col[i] - col[k] = 1, i - k = 1 이기 때문에 해당 조건을 만족해 False를 반환하게 된다. 이번 가지도 모두 탈락이다. 다시 부모 노드로 돌아가야 한다.
i = 2인 경우 - 3 ⭕
i = 2, col = [0,1,3,0,0]
이때는 promising 내의 조건문을 모두 피해갈 수 있다. 실제로 체스판에서 생각해보면 첫번째 퀸이 (1,1), 두번째 퀸이 (2,3) 에 위치한 것이 된다. 실제로 서로 공격할 수 없다.
그렇다면 else 조건으로 진입한 후 하위 노드를 테스트한다.
이런 flow로 유망하지 못한 조건들을 쳐내면서 진행하는 것이 된다. 만약 이해되지 않는다면 실제로 그려보면서 천천천히 이해해보는 것을 추천한다.
출처 : https://www.youtube.com/watch?v=HRwFgtiqHH0
https://www.youtube.com/watch?v=z4wKvYdd6wM&t=900s
수정(24/10/1) 8달 지나서야 N-Queens를 다시 풀어보았다. 이하는 파이썬(pypy)로 통과하는 코드이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import sys
read = sys.stdin.readline
# 목표: N개의 퀸이 주어졌을 때, N x N 체스판에서 만족하는 배치의 갯수
# 기본조건: 같은 행에는 둘 수 없음
# 조건1: 같은 열에는 둘 수 없음
# 조건2: 대각선에는 둘 수 없음
N = int(read())
# i: 이전에 퀸이 두어진 곳
# k: 다음행에 퀸이 두어질 곳
def promising(i, col):
for k in range(i):
if col[i] == col[k] or abs(col[i] - col[k]) == (i - k):
return False
return True
answer = 0
col = [0] * N
def n_queens(i, col):
global answer
if i == N: # 끝까지 탐사
answer += 1
return
for j in range(N):
col[i] = j
if promising(i, col):
n_queens(i+1, col)
n_queens(0, col)
print(answer)
인터넷에서 찾아보니 변수위치, 함수위치 등등에 의해 통과하지 못하는 경우도 있는 모양이다. 이번 코드는 통과했다.