BOJ_1914 : 하노이 탑

👉 문제링크

1914번: 하노이 탑

---

---

🔸 문제 분석 🔸

• 3개 장대와 N개의 원판이 있는 하노이탑 문제를 구현한다.
  • 원판을 옮긴 횟수를 출력한다.
• 원판을 옮길 때를 재귀로 나눠 구현한다.
  • 원판의 높이가 1일때와 그보다 클 때로 나눠 생각한다.
  • 예를 들어 2개의 원판을 옮길 때,
    • 첫 원판은 임시 지점에 놓는다.
    • 두 번째 원판은 목적지에 놓는다.
    • 첫 원판을 목적지의 두 번째 원판 위에 놓는다.
  • 따라서 세 막대를 시작, 임시, 목적 세 지점으로 나눠 재귀적으로 생각 할 수 있다.
• N이 너무 커지면 재귀값이 너무 커지므로 이 문제는 20보다 크면 과정 출력은 생략한다.
  • 하노이 탑의 이동 횟수는 2^N-1인데,  N이 100까지 가므로 이동 횟수가 int나 long형을 초과하게 된다.
  • 따라서 큰 수 연산이 필요하다.

🔸 코드 🔸

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

public class Main {
    private static int N;
    private static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        // Recursion
        BigInteger bigInteger1 = new BigInteger("1");
        BigInteger bigInteger2 = new BigInteger("2");
        for (int i = 0; i < N; i++) {
            bigInteger1 = bigInteger1.multiply(bigInteger2);
        }
        System.out.println(bigInteger1.subtract(new BigInteger("1")));
        if (N <= 20) {
            sb = new StringBuilder();
            hanoi(N, 1, 2, 3);
            System.out.print(sb);
        }
    }

    private static void hanoi(int n, int s, int t, int e){
        if (n == 1) {
            sb.append(s).append(' ').append(e).append('\n');
            return;
        }

        hanoi(n-1, s, e, t);
        hanoi(1, s, t, e);
        hanoi(n-1, t, s, e);
    }
}

🔸 코드 해석 🔸

• 큰 수 연산을 위해 BigInteger를 사용한다.
  • 2^N - 1 을 계산해 출력한다.
• N이 20보다 작은 경우, 재귀로 과정을 출력한다.
  • n이 1이 된 경우는 시작지 s 에서 도착지 e로 옮기면 된다.
  • n이 1보다 큰 경우는 다음과 같은 연산으로 재귀 메서드를 사용한다.
    1. 밑 바닥 원판의 위쪽을 임시 지점으로 옮긴다.
    2. 밑 바닥 원판을 목적지로 옮긴다.
    3. 임시 지점의 원판을 다시 목적지의 밑 바닥 원판 위로 옮긴다.

---

🔸 end 🔸

• 이전에 답을 보고 풀었어서 다시 풀어보았다.
  • 재귀 메서드 구현에 좋은 연습이 되는 것 같다.