yeolyi.com성열의 컴퓨터공학

백트래킹

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

스도쿠처럼 정해진 풀이 없이 채운 판이 답인지 확인만 할 수 있는 문제가 많습니다. 그럴 때는 경우의 수 글의 완전 탐색처럼 경우를 하나씩 만들어 봐야 하는데, 경우는 금방 감당할 수 없이 많아집니다. 빠짐없이, 그러면서도 덜 헤매며 만들 수는 없을까요?

N-퀸 문제

체스의 퀸은 가로, 세로, 대각선으로 몇 칸이든 가서 그 줄의 말을 잡습니다. n×n 판에 퀸 n개를 서로 잡을 수 없게 놓는 문제를 N-퀸 문제라 합니다.

퀸 4개를 놓아 봅시다.

칸을 누르면 퀸을 놓고, 퀸을 다시 누르면 뺍니다. 점은 놓인 퀸이 잡을 수 있는 칸이라 놓을 수 없습니다.

한 가로줄에 퀸이 둘이면 서로 잡으니, 줄마다 꼭 하나씩 놓입니다. 4×4면 줄마다 4칸 중 하나를 골라 곱의 법칙으로 4⁴ = 256가지, 8×8이면 1,600만 가지가 넘습니다.

재귀로 경우 만들기

줄마다 하나씩 고르는 일을 재귀로 적어 봅시다. place(row)는 row번 줄부터 끝 줄까지 퀸을 놓습니다. 줄은 0번부터 셉니다. safe는 위 줄의 퀸과 같은 세로줄이나 대각선에 있는지 봅니다. 두 칸의 가로 거리와 세로 거리가 같으면 같은 대각선입니다.

1#include <stdio.h>
2#include <stdlib.h>
3
4int n = 4;
5// queens[row]는 row번 줄 퀸의 칸
6int queens[4];
7
8int safe(int row, int col) {
9 // 위 줄의 퀸마다
10 for (int r = 0; r < row; r++) {
11 // 같은 세로줄이나 대각선이면
12 if (queens[r] == col ||
13 abs(queens[r] - col) == row - r) {
14 return 0;
15 }
16 }
17 return 1;
18}
19
20void place(int row) {
21 // 모든 줄에 놓았다
22 if (row == n) {
23 for (int r = 0; r < n; r++) {
24 printf("%d ", queens[r]);
25 }
26 printf("\n");
27 return;
28 }
29 for (int col = 0; col < n; col++) {
30 // 위 줄의 퀸에게 잡히지 않으면
31 if (safe(row, col)) {
32 queens[row] = col;
33 // 다음 줄로
34 place(row + 1);
35 }
36 }
37}
38
39int main(void) {
40 place(0);
41 return 0;
42}

변수 없음
출력 없음

row와 col이 어떻게 바뀌는지 따라가 봅시다.

safe는 끝 줄까지 다 놓은 뒤가 아니라 놓을 때마다 확인합니다. 둘째 줄에서 이미 잡히는 배치라면 아래 줄을 어떻게 채워도 답이 될 수 없으니, 더 들어가지 않고 다음 칸으로 넘어갑니다. 한 줄의 모든 칸이 막히면 함수가 끝나 윗줄로 돌아가고, 윗줄의 퀸이 옆 칸으로 옮겨 갑니다.

살펴본 칸 0

아직 아무 칸도 살펴보지 않았습니다.

찾은 답 0개 (줄마다 퀸이 놓인 칸)
아직 없음

X는 위 줄 퀸에게 잡혀 못 놓는 칸, 굵은 테두리는 그 칸을 잡는 퀸입니다.

이렇게 경우를 재귀로 만들어 가다 답이 될 수 없는 길을 알아채는 즉시 되돌아가는 방법을 백트래킹(backtracking)이라 합니다. 안 될 길을 잘라 내는 것은 가지치기(pruning)라 합니다.

가지치기의 효과

판 크기 n 4×4
모든 답을 찾을 때까지 살펴보는 칸
끝 줄까지 다 놓은 뒤 확인340
놓을 때마다 확인(가지치기)60

답은 2개이고, 가지치기로 살펴보는 칸은 약 6분의 1입니다.

8×8에서 끝 줄까지 다 놓은 뒤 확인하면 칸을 1,900만 번 넘게 살펴보지만, 놓을 때마다 확인하면 15,720번이면 92가지 답을 모두 찾습니다. 가지치기를 해도 살펴보는 칸은 n이 하나 늘 때마다 몇 배씩 늘어납니다. 그래도 일찍 자를수록 크게 줄어듭니다.

도전 문제

글의 safe를 위 줄 퀸과 같은 세로줄인지만 보도록 바꾸고, 대각선은 printf 하기 직전에 한꺼번에 확인합니다. 이렇게 바꾼 프로그램으로 5×5 판에서 place(0)을 부르면 safe는 모두 몇 번 불릴까요? 숫자로 답하세요.