[백준] 11729번 하노이 탑 이동순서 - 재귀(4) [JAVA]

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

11729번: 하노이 탑 이동 순서

---

     문제

     문제 풀이

• 전형적인 재귀함수 문제다.
• 왜 재귀인가?
  1) N개의 원판이 있을 때, 크기가 N인 마지막 원판을 1 ➡ 3으로 옮겨야한다.
  2) N - 1 개의 원판들이 모두 1 ➡ 2로 옮겨져야한다.
  3) 크기가 N - 1인 마지막 원판을 1 ➡ 2로 옮겨야한다.
  4) N - 2 개의 원판들이 모두 1 ➡ 3으로 옮겨야한다.
  ... ...
  1) ~ 4)와 같은 순서로 계속 반복될 것이다.
• Hanoi(N)은 Hanoi(N-1) + N(1 ➡ 3)이다. 
• 재귀 함수 구현시 어려웠던 점
  여기까지 알아내놓고, 구현을 못하고 있었다. 원판을 어떻게 표현해야되지?
  단순하게 1, 2, 3 을 매개 변수 start, mid, dest 로 넣으면 쉬운 거였다.
• 푼 방법
  1. N - 1 개의 원판을 start ➡ mid 로 옮긴다 ( Hanoi(start , mid) )
  2. N을 start ➡ dest 으로 옮긴다. 
  3. N - 1 개의 원판을 다시 mid ➡ dest 로 옮긴다 ( Hanoi(mid, dest) )
  -이 과정에서 다시 재귀가 들어갈 것이다.
  *이걸 못해서 한참 고민했다...
  4. base case는 무엇일까? N 이 1 일 때, 그니까 마지막 원판이 남았을 때, 그걸 destination까지 옮기면 된다.

---

        JAVA code

import java.io.*;

public class baekjoon11729 {

    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);
    }

    static void Hanoi(int N, int start, int mid, int dest) {
        // 원판이 하나일때
        if (N == 1) {
            sb.append(start + " " + dest + "\n");
            return;
        }
        // A에서 C로 옮긴다고 가정할 때,
        // Step 1 : N - 1 개를 A에서 B로 이동
        Hanoi(N - 1, start, dest, mid);
        // Step 2 : 1개를 A에서 C로 이동
        sb.append(start + " " + dest + "\n");
        // Step 3 : B로 이동된 N - 1 개를 B에서 C로 이동
        Hanoi(N - 1, mid, start, dest);
    }
}