[BaekJoon] 11729번 하노이 탑 이동 순서 (Java) 문제 풀이 [Gold 5]

문제

https://www.acmicpc.net/problem/11729

 

어떻게 풀 것인가?

컴퓨터 공학부 전공자라면 자료구조 혹은 알고리즘 수업 시간에 재귀를 공부하면서 항상 자주보는 문제였을 것 이다.

 

나는 사실 과거에 기억에 의존하여 문제를 풀었기때문에 굉장히 쉬웠지만 그래도 한번 차근차근 문제를 뜯어보자.

 

우선 하노이의 탑문제를 살펴보자.

일단, 하노이탑의 가장 큰 규칙은 "작은 원판 위에 큰 원판은 올 수 없다" 이다.

 

세 개의 기둥(A, B, C)과 여러 개의 크기가 다른 원판이 있다.
처음에는 원판들이 가장 큰 것부터 가장 작은 것까지 차례대로 한 기둥(A)에 쌓여 있다.
이 원판들을 다른 기둥(C)으로 모두 옮겨야 한다.

단, 다음과 같은 규칙을 반드시 지켜야 한다.

1. 한 번에 하나의 원판만 이동할 수 있다.
2. 작은 원판 위에 큰 원판을 놓을 수 없다.
3. 중간 기둥(B)을 보조 기둥으로 사용할 수 있다.

 

위 규칙을 상기하고 한번 공식을 찾아보자.

원판의 개수가 n개일 때, 원판을 A에서 C로 모두 옮기기 위해 다음과 같은 과정이 필요하다.

1. 가장 큰 원판을 옮기기 위해서는 나머지 (n-1)개의 원판이 A에서 B로 이동해야 한다.

• 원판이 한 개일 때는 A → C로 바로 이동하면 되지만,
• 두 개 이상일 경우, 가장 큰 원판을 옮기기 위해 위에 있는 (n-1)개의 원판을 먼저 중간 기둥(B)으로 이동해야 한다.
• 이 과정에서 다시 하노이의 탑 원리를 사용해야 한다.
• 즉, A에서 B로 (n-1)개의 원판을 옮기는 과정은 Hanoi(n-1)의 연산 횟수만큼 필요하다.

2. A에 남아 있는 가장 큰 원판을 C로 이동한다.

• 이 과정에서는 가장 큰 원판 하나만 이동하면 되므로 이동 횟수는 1이다.

3. B에 있는 (n-1)개의 원판을 C로 이동한다.

• 다시 원판 (n-1)개를 C로 옮겨야 하므로, Hanoi(n-1) 연산이 한 번 더 필요하다.

 

그러면 이제 수열로 표현할 수 있다.

n 개의 원판을 이동시키기 위해 Hanoi(n-1) 횟수만큼 이동한 횟수가 2번이고,

가장 아래 원판은 1번 이동하였으므로 공식화 하면 아래와 같다.

 

Hanoi(n) = 2 × Hanoi(n-1) + 1

자 이제 이를 코드로 한번 보자. 아래 참고

 

풀면서 놓쳤던점

하노이 탑 문제라는 것을 모르면 어려운 것 같다.

 

이 문제를 통해 얻어갈 것

재귀를 통한 문제 풀이

 

내 코드 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static BufferedReader br;
	public static BufferedWriter bw;

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		int count = (int) Math.pow(2, N) - 1;

		System.out.println(count);
		hanoi(N, 1, 2, 3);

		bw.flush();
		br.close();
		bw.close();
	}

	public static void hanoi(int n, int from, int by, int to) throws IOException {
		if (n == 0) {
			return;
		}

		hanoi(n - 1, from, to, by);
		bw.write(from + " " + to + "\n");
		hanoi(n - 1, by, from, to);
	}

}

 

참고

X