백준 1914 하노이 탑
하노이의 탑
하노이의 탑은 퍼즐의 일종입니다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판이 있고, 시작전에는 한 기둥에 원판들이 순서대로 쌓여있습니다.
게임의 목적과 조건
게임의 목적은 아래 세가지 조건을 만족 시키면서 다른 기둥으로 모든 원판을 순서대로 다시 쌓는 것입니다.
•
한 번에 한 개의 원판만 움직일 수 있다.
•
가장 위에 있는 원판만 이동할 수 있다.
•
큰 원판이 작은 원판 위에 있으면 안된다.
재귀
•
하노이의 탑은 재귀를 이용하여 풀 수 있는 가장 유명한 문제중 하나 입니다.
•
일반적으로 원판이 N 개일 때 2^N - 1 번의 이동으로 원판을 모두 옮길 수 있습니다.
구현은 어떻게 해야할까?
3개의 고리가 있고, 1번 기둥에서 3번 기둥으로 모든 고리를 옮겨야 한다고 가정 해봅시다. 위와 같은 조건을 만족 시키면서 이동하다 보면, 2번 기둥에 1, 2 번 고리가 모인다는 것을 알 수 있습니다. 그리고 나서 3 번 고리가 맨 마지막 기둥으로 이동하고, 1,2 번 고리가 다시 마지막 기둥으로 옮겨지죠.
•
1 회차
◦
1, 2 번 고리를 첫번째 기둥에서 두번째 기둥으로 옮기는 작업 수행
◦
총 3 번의 수행
•
2 회차
◦
3 번 고리를 첫번째 기둥에서 세번째 기둥으로 옮기는 작업 수행
◦
총 1 번의 수행
•
3 회차
◦
1, 2 번 고리를 두번째 기둥에서 세번째 기둥으로 옮기는 과정 수행
◦
총 3 번의 수행
문제풀이
package baekjoon.level.gold;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
public class PROB1914 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int N;
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
BigInteger count = BigInteger.valueOf(2).pow(N).subtract(BigInteger.ONE);
System.out.println(count);
if (N <= 20) {
solve(N, 1, 2, 3);
}
}
public static void solve(int n, int start, int middle, int finish) {
if (n == 0) return;
solve(n - 1, start, finish, middle);
System.out.println(start + " " + finish);
solve(n - 1, middle, start, finish);
}
}
Java
복사
T(N)
코드를 보면 각 호출은 두 개의 재귀 호출을 수행합니다. 일반적으로 T(n) 이라고 하면 다음과 같은 재귀 관계를 가집니다.
T(n) = 2T(n − 1) + 1
•
이는 출발지 기둥에서 보조 기둥으로 이동하는 재귀 호출인 solve(n - 1, start, middle, finish); 하나와
•
하나의 디스크를 출력하는 작업인 System.out.println(start + " " + finish);
•
n−1 개의 디스크를 보조 기둥에서 목적지 기둥으로 이동하는 재귀 호출인 solve(n - 1, middle, finish, start); 로 이루어져 있습니다.
•
기저조건에서는 T(0) = 0 입니다.
따라서 이를 T(3) 에 적용해보면 아래와 같습니다.
T(3) = 2T(2) + 1 → T(3) = 2(2T(1) + 1) + 1 = 2{2(2T(0) + 1) + 1} + 1 = 7
•
T(2) = 2T(1) + 1
•
T(1) = 2T(0) + 1
◦
T(0) 일때는 return 된다.