백준 11729 하노이의 탑

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

문제해결

1번, 2번, 3번 총 3개의 기둥이 있고 n개의 원판이 있을 경우 원판의 이동 순서는 다음과 같다.

만약, 원판의 개수가 n개일 경우

1. n-1개의 원판을 1번 기둥에서 2번 기둥으로 옮긴다.
2. n번째 원판을 1번 기둥에서 3번 기둥으로 옮긴다.
3. n-1개의 원판을 2번 기둥에서 3번 기둥으로 옮기면 모든 원판이 3번 기둥으로 이동하게 된다.

원판의 개수가 1개일 경우 간단하게 1번 기둥에서 3번 기둥으로 옮기면 끝이다.

소스코드

import java.io.*;

public class b11729 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        bw.write((int) Math.pow(2, n) - 1 + "\n");
        hanoi(n, 1, 2, 3);
        bw.flush();
        bw.close();
    }

    public static void hanoi(int n, int start, int middle, int end) throws IOException {
        // 이동할 원판의 개수가 1개일 경우
        if (n == 1) {
            bw.write(start + " " + end + "\n");
            return;
        }
        // 1. n-1개의 원판을 1->2번 기둥으로 이동
        hanoi(n - 1, start, end, middle);
        // 2. n번째 원판을 1->3번 기둥으로 이동
        bw.write(start + " " + end + "\n");
        // 3. n-1개의 원판을 2->3번 기둥으로 이동
        hanoi(n - 1, middle, start, end);
    }
}

회고

재귀의 대표적인 문제인 하노이의 탑. 참 거지같은 문제 중 하나였다. 처음엔 문제조차 이해가 되지 않았는데 계속 보다보니 80 퍼센트 이해했다. 하나씩 따지기 보다는 하나의 덩어리로 생각하면 빛이 보인다. 처음엔 이게 무슨 소리인지 싶겠지만 하다보면 이해할 수 있다!