[재귀] 백준 11729 하노이 탑 이동 순서 JAVA

[문제출처 | https://www.acmicpc.net/problem/11729 ]

재귀

---

학부 시절 과제로 받았던 하노이 탑...

이론은 알겠는데 이걸 코드로 짜라구요..?
눈물을 머금었더랬지

재귀의 시작, 재귀의 꽃이라 할 수 있겠다.

이론은 간단하다.
문제 설명 그대로 1번 장대에서 3번 장대로 원판을 모두 옮기는 것!

단, 크기가 제일 큰 게 맨 아래로 작은 게 맨 위에 위치하도록 한다.
옮길 땐 한 개의 원판씩, 작은 원판 위에 큰 원판이 올라갈 수 없다.

먼저 장대를 시작, temp, 최종 으로 생각하고 풀어나가도록 한다.
이동하는 횟수가 최소가 되어야 한다는 점에서 여러가지 수를 가정해야 하나? 했는데
그냥 불필요한 이동을 하지 않으면 된다..

 

이동 횟수를 먼저 출력하고 그 다음에 이동한 이력을 출력해야 했기 때문에
총 이동횟수는 전역변수(static)로 관리하고 이동 이력은 StringBuilder에 쌓아서 마지막에 출력하도록 했다.

 

---

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

// 통과 468ms
public class boj_11729_Main {
	static int ans;
	static StringBuilder sb;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();
		int k = Integer.parseInt(br.readLine());

		ans = 0;
		Hanoi('1', '2', '3', k); // 시작 원판, 중간, 최종 원판, 원판 수
		System.out.println(ans);
		System.out.println(sb);
	}
	private static void Hanoi(char a, char b, char c, int n) {
		if(n==1) { // 마지막 원반
			++ans;
			sb.append(a + " " + c + "\n");
		} else {
			Hanoi(a, c, b, n-1);
			++ans;
			sb.append(a + " " + c + "\n");
			Hanoi(b, a, c, n-1);
		}
	}
}