[백준] 11729번 : 하노이 탑 이동 순서 - JAVA [자바]

www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

---

• 문제

 

 

 

백준 단계별로 풀어보기의 재귀 문제 중 마지막 문제다.

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

이전의 재귀 문제를 그동안 풀어봤다면 이번 문제는 그리 어렵지 않은 문제다.

 

직전 문제인 별찍기 10 에서도 볼 수 있듯이 재귀를 통해 '가장 작은 단위' 가 될 때 까지 재귀호출을 하고, 가장 작은 단위까지 호출이 되었으면, 거기서 구현한 연산을 실행하면 된다.

 

 

이 문제도 같은 원리다. 하노이탑 개수와 상관없이, 일정 규칙을 찾고, 최소 단위를 생각한다면 어렵지 않게 풀 수 있다.

 

일단 하노이 탑 공식부터 알아보자.

 

 

 

 

 

[하노이 탑 원판 이동 횟수 공식 유도]

 

하노이 탑 원판 이동 횟수 공식은 워낙 유명한 공식이다보니 대부분 알고 있으리라 생각된다.

 

하지만 공식 유도 과정은 요즘은 배우는지는 몰라도 아마 많은 분들이 잊고 있거나 안배운 분들도 있을 것이라 생각되기에.. 한 번 공식을 간략하게 유도해보고자 한다.

 

 

(기초적으로 수열에 대해 이해를 하고 있다는 가정하에 공식을 유도하겠다)

 

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

위 규칙을 따르면서 다른 기둥으로 옮기기 위한 과정을 수열로 표현할 수 있어야 한다.

 

 

 

그림으로 이해해보자.

이렇게 n 개의 원판이 있다고 가정하자.

 

 

 

 

 

 

 

1. 가장 큰 원판을 C 로 옮기기 위해서는 n-1 개의 원판이 A 에서 B 로 가야한다.

 

물론 n-1 번만큼 B 로 이동하기 위한 같은 반복을 할 것이다.

즉 A 에서 B로 가는 것을 Hanoi 함수라고 한다면, n-1 개만큼 반복한다는 의미다.

즉, 이동 횟수는 Hanoi(n-1) 이다.

 

즉, 아래 그림과 같이 된다.

 

 

 

2. 그리고 A 에 있는 가장 큰 원판이 C 로 이동할 것이다.

 

이 이동은 가장 큰 원판만 이동하기 때문에 횟수는 1 회가 되겠다.

 

 

 

 

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

 

앞서 A 에서 B 로 n-1 개가 이동했듯이, B 에서 C 로 이동하는 횟수는 Hanoi(n-1) 가 된다.

 

 

 

 

 

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

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

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

 

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

 

 

이를 수학적으로 표현하자면 다음과 같다.

 

𝑛개의 원판을 이동시키기 위한 이동 횟수를 𝑎_𝑛 이라고 할 때, n개의 원판을 옮기려면 그 위 쪽에 있는 (n-1)개의 원판을 모두 다른 막대로 옮긴 후, 맨 아래 원판을 빈 막대로 옮긴 다음에 그 위에 (n-1)개의 원판을 옮겨놓아야 한다.

 

𝑎_𝑛+1 의 경우를 보면,

 

1. 가장 큰 𝑛 번째 원판을 옮기기 위해 𝑛-1 개의 원판을 옮겨야 한다. 이 때 𝑛 개의 원판이 A 에서 B 로 이동하는 경우는 𝑎_𝑛-1 이다.

 

2. 𝑛 번째 원판을 A 에서 C 로 옮기는 경우는 1 이다.

 

3. B에 있는 n개의 원판이 C로 옮기는 경우는 𝑎_𝑛-1 이다.

 

 

이 것을 수식화 하면 다음과 같다.

 𝑎_𝑛 = 𝑎_𝑛-1 + 1 + 𝑎_𝑛-1 이다.

 

즉, 원판이 이동하는 점화식은 𝑎_𝑛 = 2×𝑎_{𝑛 - 1} + 1 이다.

 

 

 

 

그럼 이 식을 귀납적으로 정리해보자.

일단 위의 수식을 통해 두 가지를 정의할 수 있다. a의 첫 번째 값은 1, 그리고 앞서 정의한 점화식이다.

 

 

위 점화식에서 양 변에 1을 더해 우변을 다음과 같이 묶어줄 수 있다.

 

 

그리고 임의의 b_n을 다음과 같이 정의해보자.

 

그럼 우리는 a로 표현된 식을 다음과 같이 표현 할 수 있다. 이는 곧 공비가 2임을 말한다.

 

그리고 b_n의 첫째항, 즉 b₁은 a₁ = 1 이었으므로 다음과 같겠다.

 

즉, 첫째항은 2이고, 공비는 2 인 '공비수열'이 된다.

 

이를 풀어내면 다음과 같다.

 

이 공식의 일반항은 𝑎_𝑛 = 2ⁿ- 1  이다.

 

 

 

 

 

 

 

그러면 일단 첫 번째 출력해야할 원판 이동 횟수는 풀렸다.

n 을 입력받으면 2의 n승을 한 뒤 -1 을 해준 값을 출력하면 된다.

 

 

 

 

 

 

 

 

[재귀 알고리즘 접근방법]

 

사실 앞서 공식을 유도하면서 거의 90% 설명이 끝난 것이나 마찬가지다.

 

 

일단 재귀를 통해 가장 작은 단위로 들어간다.

즉, 먼저

A 에서 B 로 원판을 이동하는 경우의

    A 에서 B 로 원판을 이동하는 경우의

        A 에서 B 로 원판을 이동하는 경우의

                      ...

 

이렇게 계속 A 에서 B로 이동하는 함수를 재귀호출하여 이동해야 할 원판이 1개가 되면 그 때 A 에서 B로 이동했다는 것을 출력한 뒤, 함수를 리턴하면 된다.

 

그렇게 원판이 1개일 때 A 에서 B로 이동한 함수가 닫히면

그 전 단계 재귀로 다시 돌아오면 원판이 2개일 때가 된다. 이때는 앞서 그림에서 봤듯이 1개의 원판이 A 에서 C로 이동하면 되므로, 이 때의 경우를 출력한다.

 

출력이 끝나면, B 에서 C 로 이동하도록 다시 재귀호출을 한다.

 

이 메커니즘을 그대로 반영하면 된다.

 

 

위키트리에서 잘 설명해주고 있으니 아래를 참고하면 되겠다.

ko.wikipedia.org/wiki/하노이의_탑

하노이의 탑 - 위키백과, 우리 모두의 백과사전

 

 

즉, 기본적인 재귀함수 기본 골자는 아래와 같이 구성하면 된다.

 

 

/*
	N : 원판의 개수
	start : 출발지
	mid : 옮기기 위해 이동해야 장소
	to : 목적지
*/

void Hanoi(int N, int start, int mid, int to) {

	// 이동할 원반의 수가 1개라면?
	if (N == 1) {
		print(start + " " + to + "\n");
		return;
	} 

	// A -> C로 옮긴다고 가정할 떄,
	// STEP 1 : N-1개를 A에서 B로 이동 (= start 지점의 N-1개의 원판을 mid 지점으로 옮긴다.)
	Hanoi(N - 1, start, to, mid);
    
	// STEP 2 : 1개를 A에서 C로 이동 (= start 지점의 N번째 원판을 to지점으로 옮긴다.)
	print(start + " " + to + "\n");
    
	// STEP 3 : N-1개를 B에서 C로 이동 (= mid 지점의 N-1개의 원판을 to 지점으로 옮긴다.)
	Hanoi(N - 1, mid, start, to);
	
}

 

 

 

 

 

 

 

 

 

 

 

 

---

• 4가지 방법을 이용하여 풀이한다.

 

먼저 알고리즘은 위에서 보여준 기본 골자를 토대로 작성할 것이다.

 

다만, 입력과 출력을 달리하여 보여주려 한다.

입력은 Scanner 와 BufferedReader 을 통한 방법으로 보여줄 것이다.

출력의 경우는 StringBuilder 와 BufferedWriter 을 사용할 것이다.

 

자바의 경우는 출력함수인 System.out.println() 의 경우도 반복적으로 호출하면 성능이 매우 떨어진다.

 

그렇기에 기본적으로 StringBuilder 또는 BufferedWriter 을 써주는 것이 좋다.

 

테스트해보니까 Scanner 을 쓸 경우 매 번 출력해주게 되면 시간초과가 난다.

 

---

• 풀이

- 방법 1 :  [ Scanner + StringBuilder() ]

 

import java.util.Scanner;

public class Main {

	public static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int N = in.nextInt();

		sb.append((int) (Math.pow(2, N) - 1)).append('\n');

		Hanoi(N, 1, 2, 3);
		System.out.println(sb);

	}

	/*
		N : 원판의 개수 
		start : 출발지 
		mid : 옮기기 위해 이동해야 장소 
		to : 목적지
	 */

	public static void Hanoi(int N, int start, int mid, int to) {
		// 이동할 원반의 수가 1개라면?
		if (N == 1) {
			sb.append(start + " " + to + "\n");
			return;
		}

		// A -> C로 옮긴다고 가정할 떄,
		// STEP 1 : N-1개를 A에서 B로 이동 (= start 지점의 N-1개의 원판을 mid 지점으로 옮긴다.)
		Hanoi(N - 1, start, to, mid);
    
		// STEP 2 : 1개를 A에서 C로 이동 (= start 지점의 N번째 원판을 to지점으로 옮긴다.)
		sb.append(start + " " + to + "\n");
    
		// STEP 3 : N-1개를 B에서 C로 이동 (= mid 지점의 N-1개의 원판을 to 지점으로 옮긴다.)
		Hanoi(N - 1, mid, start, to);

	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

알고리즘은 그대로 적용했고, 각 스텝별로 주석을 달았으니 한 번 n = 3 일 때 부터 직접 디버그를 해보시는 것도 좋은 방법이 될 것이다.

 

 

 

 

---

 

 

- 방법 2 : [ Scanner + BufferedWriter ] 

 

 

StringBuilder 와 BufferedWriter 는 모두 빠른 출력 성능을 보여주기에 어느 것을 선택해도 무방하다.

다만 이러한 방법도 있다는 것 정도는 알아두시면 좋을 것 같다.

 

 

import java.util.Scanner;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;

public class Main {

	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(System.in);

		int N = in.nextInt();

		bw.write((int) (Math.pow(2, N) - 1) + "\n");

		Hanoi(N, 1, 2, 3);
		bw.flush();
		bw.close();

	}

	/*
		N : 원판의 개수 
		start : 출발지 
		mid : 옮기기 위해 이동해야 장소 
		to : 목적지
	 */

	public static void Hanoi(int N, int start, int mid, int to) throws IOException {
		// 이동할 원반의 수가 1개라면?
		if (N == 1) {
			bw.write(start + " " + to + "\n");
			return;
		}

		// A -> C로 옮긴다고 가정할 떄,
		// STEP 1 : N-1개를 A에서 B로 이동 (= start 지점의 N-1개의 원판을 mid 지점으로 옮긴다.)
		Hanoi(N - 1, start, to, mid);
    
		// STEP 2 : 1개를 A에서 C로 이동 (= start 지점의 N번째 원판을 to지점으로 옮긴다.)
		bw.write(start + " " + to + "\n");
    
		// STEP 3 : N-1개를 B에서 C로 이동 (= mid 지점의 N-1개의 원판을 to 지점으로 옮긴다.)
		Hanoi(N - 1, mid, start, to);

	}
}

 

 

 

 

 

---

 

 

- 방법 3 : [ BufferedReader + StringBuilder() ] 

 

 

 

입력에서 시간을 가장 단축 할 수 있는 방법 중 하나다. 백준에서 Scanner 는 한 번만 입력받더라도 기본 수행시간이 100ms 를 넘어간다.

그렇기 때문에 대부분 각 문제별로 Java 제출자 중 시간이 상위권인 분들은 BufferedReader 을 많이 사용한다.

 

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

public class Main {

	public static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		sb.append((int) (Math.pow(2, N) - 1)).append('\n');

		Hanoi(N, 1, 2, 3);
		System.out.println(sb);

	}

	/*
		N : 원판의 개수 
		start : 출발지 
		mid : 옮기기 위해 이동해야 장소 
		to : 목적지
	 */

	public static void Hanoi(int N, int start, int mid, int to) {
		// 이동할 원반의 수가 1개라면?
		if (N == 1) {
			sb.append(start + " " + to + "\n");
			return;
		}

		// A -> C로 옮긴다고 가정할 떄,
		// STEP 1 : N-1개를 A에서 B로 이동 (= start 지점의 N-1개의 원판을 mid 지점으로 옮긴다.)
		Hanoi(N - 1, start, to, mid);
    
		// STEP 2 : 1개를 A에서 C로 이동 (= start 지점의 N번째 원판을 to지점으로 옮긴다.)
		sb.append(start + " " + to + "\n");
    
		// STEP 3 : N-1개를 B에서 C로 이동 (= mid 지점의 N-1개의 원판을 to 지점으로 옮긴다.)
		Hanoi(N - 1, mid, start, to);
	}
}

 

 

특히 형 변환 해줄 때 유의하셔야 한다.

 

 

 

 

 

 

---

 

 

 

- 방법 4 : [ BufferedReader + BufferedWriter ] 

 

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

public class Main {

	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		bw.write((int) (Math.pow(2, N) - 1) + "\n");

		Hanoi(N, 1, 2, 3);
		
		bw.flush();
		bw.close();
	}

	/*
		N : 원판의 개수 
		start : 출발지 
		mid : 옮기기 위해 이동해야 장소 
		to : 목적지
	 */

	public static void Hanoi(int N, int start, int mid, int to) throws IOException {
		// 이동할 원반의 수가 1개라면?
		if (N == 1) {
			bw.write(start + " " + to + "\n");
			return;
		}

		// A -> C로 옮긴다고 가정할 떄,
		// STEP 1 : N-1개를 A에서 B로 이동 (= start 지점의 N-1개의 원판을 mid 지점으로 옮긴다.)
		Hanoi(N - 1, start, to, mid);
    
		// STEP 2 : 1개를 A에서 C로 이동 (= start 지점의 N번째 원판을 to지점으로 옮긴다.)
		sb.append(start + " " + to + "\n");
    
		// STEP 3 : N-1개를 B에서 C로 이동 (= mid 지점의 N-1개의 원판을 to 지점으로 옮긴다.)
		Hanoi(N - 1, mid, start, to);

	}
}

 

 

 

크게 설명할 것은 없을 것이다.

혹여나 모르거나 이해가 안되는 부분이 있다면 댓글 남겨주시길 바란다.

 

최대한 빨리 답변드리겠다.

 

 

 

 

 

 

 

 

---

• 성능

위에서 부터 순서대로

 

채점 번호 : 19840016  -  방법 4 : BufferedReader + BufferedWriter

채점 번호 : 19840012  -  방법 3 : BufferedReader + StringBuilder

채점 번호 : 19840008  -  방법 2 : Scanner + BufferedWriter

채점 번호 : 19840005  -  방법 1 : Scanner + StringBuilder

 

 

이번 문제는 직전 문제와는 달리 BufferedWriter 보다 StringBuilder 의 퍼포먼스가 더 좋다는 것을 알 수 있다.

(물론 메모리는 StringBuilder 가 더 많이 차지한다..)

 

 

 

---

• 정리

 

재귀의 마지막 문제인 하노이 탑 이동 순서가 끝났다.

 

사실 재귀 카테고리로 넘어오면서 이를 어떻게 설명해야지 글로도 전달이 잘 될까 고민을 가장 많이했던 카테고리이기도 하다.

아마 글로도 이해가 안되시는 분이 분명 있을 것이라 본다.

 

만약 이해가 안간다면 댓글 달아주면 최대한 열심히 답변하도록 하겠다.

 

물론 코드는 필자가 공유하긴 하나.. 그대로 복붙해서 통과에만 목적을 둔다면.... 글쎼.. 필자는 그렇게 하면 정말 힘든 분야 중 하나가 프로그래밍 언어로 무언가를 개발하는 부분이라고 생각하기에 추천드리진 않는다.

 

여튼 재귀 카테고리 끝!