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

📌 출처

11729번 : 하노이 탑 이동 순서

📝 문제

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

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

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

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

⌨ 입력

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

🖨 출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

💻 내 코드

1. 리스트를 사용하여 구현

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

public class p11729 {
    private static int cnt = 0;
    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());

        hanoi(N, 1, 2, 3);

        System.out.println(cnt);
        System.out.println(sb);
    }

    private static void hanoi(int n, int start, int mid, int end) {
        cnt++;

        if(n==1) {
            sb.append(start + " " + end + "\n");
            return;
        }

        hanoi(n-1, start, end, mid);
        sb.append(start + " " + end + "\n");
        hanoi(n-1, mid, start, end);

    }
}

✏ 설명

하노이 탑은 유명한 공식이 있다고 한다.
일단 그걸 모른다는 전제하에 유도를 해보겠다.

1. n개의 원판이 1번 기둥에 쌓여있다.
2. 가장 큰 원판을 3번 기둥으로 옮기기 위해서는 n-1개의 원판이 1번에서 2번으로 가야 한다.
   즉, 이동 횟수는 Hanoi(n-1)이다.
3. 그리고 1번에 있는 가장 큰 원판이 3번으로 이동할 것이다.
   이 때의 이동 횟수는 1이다.
4. 2번에 있는 n-1개의 원판을 3번으로 이동한다.
   이 때의 이동 횟수는 Hanoi(n-1)이다.

이를 수열로 표현하면 다음과 같다.

$a_n=Hanoi(n)$이라고 하면 위 식을 다음과 같이 정리할 수 있다.

위 식에 양 변에 1을 더해 우변을 다음과 같이 묶어줄 수 있다.

이 때 $b_n=a_n+1$이라고 하면 다음과 같이 표현할 수 있다.

즉, 첫째항은 2이고, 공비는 2인 공비수열이 된다.
이를 풀어내면 다음과 같다.

즉, 하노이 탑에서 원판의 이동 횟수는 $2^n-1$인 것이다.

해당 식을 이용해서 출력해도 되지만 나는 $a_n=2*a_{n-1}+1$식을 사용하여 문제를 해결하였다.

앞으로 하노이 탑 문제가 나오면 해당 식을 떠올리자.