[백준] 11729 : 하노이 탑 이동 순서

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

 

• 알고리즘

1. 원반이 한개면 그냥 옮기면 끝이다.(종료조건)
2. 원반이 n 개 일때
   1. 1번 기둥에 있는 n개 원반 중 n-1 개를 목적지가 아닌 보조기둥(2번)으로 옮긴다.
   2. 1번 기둥에 남아 있는 가장 큰 원반을 목적지(3번) 기둥으로 옮긴다.
   3. 2번 기둥에 있는 n-1 개 원반을 다시 목적지(3번) 기둥으로 옮긴다.

원반이 1 개일 때가 '종료 조건' 에 해당한다. 원반 n 개 문제를 풀려면 n-1 개 원반 문제를 풀어야 하는데 이는 바로 '좀 더 작은 값으로 자기 자신을 호출하는 과정'이다. 따라서 이 문제는 전형적인 재귀 호출 알고리즘에 해당한다(이승찬, 2017)

 

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

class Main{
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {
        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,3,2);
        System.out.println(sb);
    }

    public static void Hanoi(int n, int start, int end, int mid){
        if(n == 1){
            // 탈출조건
            sb.append(start).append(" ").append(end).append("\n");
            return;
        }

        Hanoi(n-1, start, mid, end); // A. (n-1) 개의 원판 : 현재 상태 (start) -> 목적지가 아닌곳
        sb.append(start).append(" ").append(end).append("\n"); // B. n 번쨰 원판 (가장큰 원판) : 현재 위치 -> 목적지
        Hanoi(n-1, mid, end, start); // C. 목적지가 아닌 곳 (A에서 옮기 (1~n-1) 개의 원판) -> 목적지
    }

}

 

TIP : 이해가 안된다면 그림을 그려보자!