Backtracking 방식의 기본원리
현재 노드까지의 상태를 볼 때, 여기서 진행하여 목표를 달성할 수 있을까? (유망한가?)
- 유망하지 않은 경우 : 함수를 종료한다 / 유망한 경우 : 아래의 과정을 진행한다
* 현재 노드까지의 결과가 곧 정답이 되는 경우 : 정답을 리턴한다
- 현재 노드에서 더 진행해야 결과가 나오는 경우 : 각 child들에 대해 함수를 재귀호출한다.
n-Queens Problem
n by n 크기의 체스판이 있다고 하자. 이때 n개의 Queen을 서로 "공격하지 못하도록" 체스판 위에 위치시키고자 한다. (Queen은 앞, 뒤, 좌우, 대각선의 8방향으로 무한정 이동할 수 있다).
예를 들어, 4 * 4 체스판 위에 4개의 Queen을 위치시키는 방법에는 다음의 방법이 존재한다.
. Q . .
. . . Q
Q . . .
. . Q .
몇 번 시행착오를 겪어 보면 알겠지만, 결국 Queen은 모든 행, 모든 열에 각각 하나씩만 위치하게 된다.
알고리즘 설명
- col[i] - i번째 Queen이 위치한 column의 값 (i번째 Queen이란, i번째 row에 위치한 Queen을 의미한다. 즉, 하나의 row에 하나의 Queen이 위치함은 미리 가정하고 시작한다)
Queens 함수 (i를 입력으로 받음)
- 현재까지의 col 배열이 유망한지를 Promising 함수를 이용하여 판단한다 (Promising 함수는 아래에 정의)
- 유망하지 않은 경우 결과값 없이 함수를 종료하고, 유망한 경우에는 아래의 과정을 시행한다
2-1. 현재 col 배열이 정답이 되는 경우 (i == n인 경우) : col 배열을 출력한다
2-2. 과정을 더 진행해야 하는 경우 (i != n인 경우) : col[i+1]의 값을 1부터 n까지 할당하고, 각 경우에 대해 Queens 함수를 재귀호출한다.
Promising 함수 (i를 입력으로 받음)
- k = 1, switch = True로 설정한다
- i보다 작은 범위 내에서 k를 하나씩 증가시키면서, 아래의 과정을 반복한다. (switch가 False인 경우 탈출)
2-1. i, k번째 Queen이 서로 같은 열에 위치하거나, 대각선상에 위치하는 경우, switch를 False로 변경한다
2-1. k를 1 증가시키고, 과정을 반복한다.
위의 과정을 pseudo code로 나타내면 아래와 같다.
부분집합의 합 구하기 (Sum of Subsets Problem)
n개의 item을 이용하여, item의 무게의 합이 W가 되는 부분집합을 구하는 문제
예시) w1 = 2, w2 = 4, w3 = 5, W = 6인 경우, {w1, w2}의 유일한 정답을 가진다.
문제풀이 전략
우선, item 들을 무게가 증가하는 순으로 정렬한다. 이렇게 하면 현재까지의 결과가 유망한지 아닌지를 쉽게 판단할 수 있게 된다. 가령, 현재 현재까지의 상태에서 남은 무게가 10인데 바로 다음 item의 무게가 12인 경우, 그 뒤의 item들은 볼 것도 없이 현재 상태는 유망하지 못하다. 이때 현재 상태가 유망한지 아닌지는 아래의 기준을 통해 정해진다.
- 현재 상태에서 바로 다음 item을 추가하면 W를 넘는 경우, 유망하지 않다.
- 현재 상태에서 남은 모든 item을 추가해도 W가 되지 않는 경우, 유망하지 않다.
- 1, 2번 조건에 모두 해당하지 않는 경우, 유망하다.
- 변수를 아래와 같이 정의한 후, 아래의 pseudo code를 보자.
weight : 현재 수준까지 포함된 무게의 총 합
total : 남아 있는 item의 무게의 총 합
include : w1 ~ wn에 대해, 각 item을 포함할지 아닐지에 대한 boolean 배열
문제 해결 과정을 Space-State Tree (상태공간트리)로 나타낼 때, 문제풀이의 진행 과정은 이 Tree에 대한 Depth-First-Search 순서와 유사하다.
M - Coloring Problem
지도를 M가지 색을 이용하여 서로 겹치지 않게 색칠하자
문제풀이 전략
지도를 그래프로 변환한다
그래프로 변환된 경우, 그래프 구조를 행렬로 표현할 수 있다.
유망한지의 여부 판단 방법
매우 간단한데, 서로 연결되어 있으면서 같은 색인 관계가 존재하는 경우 유망하지 않다
용어 정의
W : 그래프 구조를 나타내는 행렬이다. 각 원소는 Bool이며, W[i][j]는 i노드와 j노드가 서로 연결되어 있는지의 여부를 나타낸다.
vcolor : 각 노드의 색상을 나타내는 1차원 배열이다. vcolor[i]는 i번째 노드의 색상을 의미한다.
m : 문제에서 주어진 색상의 수를 의미한다. m = 4인 경우 그 유명한 4색 문제가 된다.
이를 토대로 아래의 코드를 보자.
