[BOJ11729] 하노이 탑 이동 순서

백준 11729 하노이 탑 이동 순서 

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

11729번: 하노이 탑 이동 순서

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

 

이 문제에서는 '하노이 탑'에 집중할 것이 아니라 '재귀'에 집중을 해야한다. 어떤 것을 얼마나 반복해주어야 하는것인지가 중요하다.

그렇다면 재귀, 어떻게 풀어야할까?

1. 종료 구문
2. 규칙 찾기

당연히 함수를 반복해주는 것에 있어서는 언제 종료할 것인지가 중요하다. 

이 문제에서는 모든 원판이 다른 장대로 이동하는 것이 종료할 시점이 된다.

 

규칙은 원판이 1개일 때부터 차분히 세어보았다.

원판이 1개일 때 -> 1번

원판이 2개일 때 -> 3번

원판이 3개일 때 -> 7번

원판이 4개일 때 -> 15번

..

이후는 안세었다 나도 헷갈려서.. 무튼 여기까지만 세어도 규칙은 대충 보인다. 1개일 때는 1, 2일때부터는 2의 n제곱 -1이 되는 것.

그래서 최소 이동 횟수는 따로 생각해주지 않고 이후부터는 이동 순서에 집중해보기로 했다.

 

가장 먼저 든 생각은 절대 한 번에 이동 순서를 리턴할 수는 없겠다는 것이었다. 경우의 수도 많아질 뿐더러, 그렇게 되면 이동 횟수가 최소인 이동 순서가 나오지 않기 때문이다.

(ㅠㅠ 여기까지가 나의 한계였다.)

도저히 이동 순서를 어떻게 계산할 지 감이 오지 않아 다른 분들의 코드를 참고해보았다.

 

세번째 장대로 모두 옮기기 위해 가장 먼저 해야할 일은 가장 큰 원판을 세번째 장대에 두는 것. 그래야 그 위에 작은 원판들을 쌓을 수 있기 때문이다. 

첫번째 장대의 가장 큰 원판이 세번째 장대로 가기 위해서는 두번째 장대를 거쳐야한다. 그리고 나서 두번째 장대를 세번째로 옮겨주는 것.

 

이 두 줄이 문제의 끝이다.

 

정답 코드는 아래와 같다. 1년 전에는 어떻게 풀었는가 몰라.. 

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

public class BOJ11729 {
    private 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 + "\n"); //최소

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

    private static void hanoi(int A, int mid, int B, int N) { //A : 출발, mid : 경유, B : 도착
        if (N == 1) { //탈출 조건
            sb.append(A + " " + B + "\n"); //
            return;
        }

        //일단 첫번째 원판에서 두번째로 하나빼고 다 옮겨! (경유)
        hanoi(A, B, mid, N - 1);  // N-1

        // 그러면 첫번째 원판에 하나 남겠찌? 그거 세번째로 옮겨! (도착!)
        sb.append(A + " " + B + "\n");

        //이제 두번째 원판꺼 세번째 원판으로 다 옮겨!
        hanoi(mid, A, B, N - 1);
    }
}