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

문제

- 우리가 흔히 알고 있는 하노이 탑 이동 순서를 출력하는 문제

- 세 개의 장대가 있고, 첫 번째 장대에서 세 번째 장대로 다음 규칙에 따라 원판을 이동

   1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.

   2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

- 이 작업을 수행하는데 필요한 최소의 이동 횟수와 이동 순서를 출력하는 프로그램 작성

 

고찰

오랜만에 다시 알고리즘을 풀기 시작했기 때문에 쉬운 단계부터 다시 도전해야겠다고 생각하였다.

백준에서 단계별 풀기로 재귀부터 시작했는데 오랜만에 문제를 풀어서 그런지 바로바로 아이디어가 떠오르지 않았다.

 

첫 번째 장대에서 시작해서 세 번째로 옮길 때, 전체를 두 덩어리(n-1개, 1개 - 맨 밑)로 나눠 이동시켰다.

두 덩어리 중 맨 밑에 있는 1개를 먼저 목표 지점으로 옮기고 나머지를 중간 지점(mid)로 이동시켰다.

from, mid, to 기둥은 계속해서 바뀌기 때문에 매개변수로 전달하였다.

 

코드

import java.io.*;
import java.util.*;

class Main{
    static StringBuilder sb = new StringBuilder();
    static int count;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        hanoi(N, 1, 2, 3);
        System.out.println(count);
        System.out.println(sb);
    }

    static void hanoi(int n, int from, int mid, int to){
        count++;
        if(n == 1){
            sb.append(from).append(" ").append(to).append("\n");
            return;
        }

        hanoi(n-1, from, to, mid);
        sb.append(from).append(" ").append(to).append("\n");
        hanoi(n-1, mid, from, to);
    }
}