오늘은 재귀 알고리즘을 응용하여 풀 수 있는 문제들을 풀어보자.
📘 하노이의 탑
하노이의 탑(Towers of Hanoi)은 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제이다.
모든 원반은 크기가 다 다르고 처음에는 모든 원반이 규칙에 맞게 첫 번째 기둥에 쌓여 있다. 이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮기면 된다.
예를 들어 원반이 3개가 있다고 생각해보자.
작은 원반순으로 숫자 1,2,3으로 나타내고 차례대로 움직여보면
(1) 원반 1을 첫 번째 기둥에서 세 번째 기둥으로 옮김
(2) 원반 2를 첫 번째 기둥에서 두 번째 기둥으로 옮김
(3) 원반 1을 세 번째 기둥에서 두 번째 기둥으로 옮김
(4) 원반 3을 첫 번째 기둥에서 세 번째 기둥으로 옮김
(5) 원반 1을 두 번째 기둥에서 첫 번째 기둥으로 옮김
(6) 원반 2를 두 번째 기둥에서 세 번째 기둥으로 옮김
(7) 원반 1을 첫 번째 기둥에서 세 번째 기둥으로 옮김
이렇듯 7번의 과정이 수행이 된다.
여기서 처음에 원반 1을 세 번째 기둥이 아닌 두 번째 기둥으로 옮겨도 되지만 이렇게 한다면 최소의 횟수로 이동을 마칠 수가 없다.
✏ 하노이의 탑 코드
코드롤 작성하여 한번 알아보자.
import java.util.Scanner;
public class Hanoi {
// num개의 원반을 x번 기둥에서 y번 기둥으로 옮김
static void move(int num, int x, int y) {
if (num > 1)
move(num - 1, x, 6 - x - y);
System.out.println("원반[" + num + "]을 " + x + "기둥에서 " + y + "기둥으로 옮김");
if (num > 1)
move(num - 1, 6 - x - y, y);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("원반의 갯수 : ");
int n = sc.nextInt();
// 1번 기둥의 n개의 원반을 3번 기둥으로 옮김
move(n, 1, 3);
}
}하노이의 탑 문제는 재귀 알고리즘으로 풀 수가 있다.
이 코드에서 기둥 번호를 정수 1, 2, 3으로 표현했다. 기둥 번호의 합이 총 6이므로 시작하는 기둥, 목표하는 기둥이 어디라도 중간에 있는 기둥은 6-x-y로 구할 수 있다. 원반은 num개 이므로 move메서드를 사용하여 재귀를 이용해서 풀 수 있다.
move메서드는 다음과 같은 과정을 거친다.
(1) 바닥 원반을 제외한 그룹(원반[1] ~ 원반[num - 1])을 시작 기둥에서 중간 기둥으로 옮긴다.
(2) 바닥 원반 no를 시작 기둥에서 목표 기둥으로 옮겼음을 출력
(3) 바닥 원반을 제외한 그룹(원반[1] ~ 원반[num - 1])을 중간 기둥에서 목표 기둥으로 옮긴다.
📘 8퀸 문제
"서로 공격하여 잡을 수 없도록 8개의 퀸을 8 X 8 체스판에 놓아라."
8퀸 문제는 하노이의 탑과 같이 재귀 알고리즘을 활용하면 풀 수 있다. 이 문제는 19세기의 유명한 수학자 카를 프리드리히 가우스(C. F. Gauss)가 잘못된 해답을 낸 사실로도 잘 알려진 문제이다.
✏ 퀸 배치하기
8개의 퀸을 배치하는 조합을 구해보자.
체스판은 64칸(8X8)이므로 처음에 퀸 1개를 배치할 땐 64칸 중 아무 곳이나 선택할 수 있다. 다음 퀸을 배치할 땐 나머지 63칸에서 임의로 선택한다.
=> 64 X 63 X 62 X 61 X 60 X 59 X 58 X 57 = 178,462,987,637,760 이다.
근데 이 조합을 모두 나열한 후에 조건을 만족하는지 조사하는 것은 현실적이지 못하다. 그래서 규칙을 하나 추가해보았다.
[규칙 1] 각 열에는 퀸을 1개만 배치하자.
이렇게 하면 퀸을 배치하는 조합의 수는 많이 줄었지만 여전히
8 X 8 X 8 X 8 X 8 X 8 X 8 X 8 = 16,777,216 가지이다.
규칙을 한가지 더 추가해보자.
[규칙 2] 각 행에는 퀸을 1개만 배치하자.
이렇게 하면 배치할 수 있는 방법을 많이 줄어든다.
✏ 8퀸 코드
8퀸 문제를 코드로 알아보자.
public class EightQueen {
static boolean[] check = new boolean[8]; // 각 행에 퀸을 배치했는지 체크
static boolean[] check_a = new boolean[15]; // '/'대각선 방향으로 퀸을 배치했는지 체크
static boolean[] check_b = new boolean[15]; // '\'대각선 방향으로 퀸을 배치했는지 체크
static int[] position = new int[8]; // 각 열의 퀸의 위치
// 각 열의 퀸의 위치를 출력
static void print() {
for (int i = 0; i < 8; i++)
System.out.printf("%2d", position[i]);
System.out.println();
}
// i열에 알맞은 위치에 퀸을 배치
static void set(int i) {
for (int j = 0; j < 8; j++) {
if (check[j] == false && check_a[i + j] == false && check_b[i - j + 7] == false) {
position[i] = j;
if (i == 7)
print();
else {
check[j] = check_a[i + j] = check_b[i - j + 7] = true;
set(i + 1);
check[j] = check_a[i + j] = check_b[i - j + 7] = false;
}
}
}
}
public static void main(String[] args) {
set(0);
}
}check_a와 check_b는 각각 대각선 방향에 퀸을 배치했는지 체크하는 배열이다.
가로 방향, 왼쪽 대각선 방향, 오른쪽 대각선 방향 중 어느 방향이든 1개의 라인이라도 퀸이 배치되었다면 그 칸에는 퀸을 놓을 필요가 없다.
3개의 판단하는 배열을 사용하는 한정 조작을 사용하면 퀸의 배치를 효율적으로 할 수 있다. 프로그램을 실행하면 92개의 조합이 출력이 된다.
