[11729] 하노이 탑 이동 순서

문제 링크 : https://www.acmicpc.net/problem/11729

11729 - 하노이 탑 이동 순서

본문

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

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

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

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

입력

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

출력

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

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

제한

시간 제한	메모리 제한
1sec	256MB

---

풀이

유명한 하노이 탑 문제다. 규칙과 조건을 지키면서 1번 장대에 있는 원판들을 모두 3번 장대로 옮기면 되는 문제이다.

하노이 탑을 옮기는 기본적인 방법은 크게 3가지 단계로 나눌 수 있다.

1. 가장 아래 원판을 제외한 모든 원판들을 빈 장대로 모두 옮긴다

2. 가장 아래 원판을 원하는 장대 위치로 옮긴다

3. 1단계에서 옮겼던 원판들을 모두 원하는 장대 위치로 옮긴다

한 무더기의 원판들은 모두 위와 같은 과정으로 옮길 수 있으므로, 재귀함수를 이용하면 간단하게 구현할 수 있다.

• 참고 알고리즘 :

코드

사용 언어 : C

최종 수정일 : 2024 / 3 / 18

#include <stdio.h>

const int FIRST = 1, MIDDLE = 2, LAST = 3, ALL = 6;
int n;

void print_hanoi(int x, int s, int e) {
    if (x == 1) {
        printf("%d %d\n", s, e);
    } else {
        print_hanoi(x - 1, s, ALL - s - e);
        printf("%d %d\n", s, e);
        print_hanoi(x - 1, ALL - s - e, e);
    }
    return;
}

int main() {
    scanf("%d", &n);

    printf("%d\n", (1 << n) - 1);
    print_hanoi(n, FIRST, LAST);
    return 0;
}