[백준 11729/Java] 하노이 탑 이동 순서

 

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

 

---

✨ 참고

https://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%91

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

https://st-lab.tistory.com/96

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

https://shoark7.github.io/programming/algorithm/tower-of-hanoi

'하노이의 탑' 이해하기

---

 

풀이

• 먼저 맨 밑에 있는 원판을 제외한 n-1개의 원판을 경유 막대로 이동시킨다.
• 맨 밑에 있는 원판을 목적 막대로 이동시킨다.
• 경유 막대에 있는 n-1개의 원판을 다시 목적 막대로 이동시킨다.
  • n개의 원판을 옮긴 횟수를 A(n)이라고 하면 A(n) = 2 * A(n-1) + 1
  • = 2^(n) - 1

4개의 원반을 이동시키기 위해선 먼저 그 위에 있는 3개의 원반을 이동시켜야 하고, 해당 3개의 원반을 옮기기 위해선 맨 위에 있는 2개의 원반을 옮겨야한다. 이렇게 재귀적인 호출이 이루어진다.

 

코드

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 BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void movePlate(int n, int from, int mid, int to) throws IOException {
		if (n == 1) {	// 옮길 원반이 1개인 경우
			bw.write(from + " " + to + "\n");
			return;
		}
		
		movePlate(n-1, from, to, mid);
		bw.write(from + " " + to + "\n");	// 가장 큰 원반 옮기기
		movePlate(n-1, mid, from, to);
	}

	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");
		
		movePlate(n, 1, 2, 3);
		
		bw.close();
	}

}