[Baekjoon/Silver 2/C, C++] 11729번: 하노이 탑 이동 순서

Baekjoon(백준) 11729번: 하노이 탑 이동 순서

11729번: 하노이 탑 이동 순서

문제 설명

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

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

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

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

예)
입력:
3
출력:
7
1 3
1 2
3 2
1 3
2 1
2 3
1 3

풀이

이 문제에서는 풀어야 할 작은 문제가 2개 있다.

1) 원판을 옮긴 횟수 출력
2) 원판 옮기는 과정 출력

둘다 재귀를 이용해서 간단하게 풀 수 있다.

(1)의 경우, 하노이 탑 원판의 개수에 따라 횟수가 어떻게 증가하는지 규칙을 찾으면 쉽게 풀 수 있다.
결론부터 말하면, 원판이 n개일 때 옮긴 횟수가 count(n)라면, count(n) = count(n-1) * 2 + 1이다.
원판이 4개라고 하면, 원판 3개를 1번째 탑에서 2번째 탑으로 옮기고 난 후(count(3)번 원판 이동), 마지막 원판을 3번째 탑으로 옮기고(1번 원판 이동), 2번째 탑에 있는 3개의 원반을  3번째 탑으로 옮긴다(count(3)번 원판 이동).

위 규칙을 이용해 정의한 원판을 옮긴 횟수를 구하는 함수는 다음과 같다.

/**
 * 원판 옮긴 횟수 구하는 함수
 * @param n 원판 개수
 * @return 옮긴 횟수
 */
int count_hanoi_tower(int n)
{
    if(n == 1) return 1;
    else return 2 * count_hanoi_tower(n-1) + 1;
}

 

(2)의 경우는 하노이 탑 원판을 옮기는 과정을 출력해야 한다. 이 역시 위에서 언급한 규칙을 가지고 구현할 수 있다.
원판이 n개를 1번째 탑에서 3번째 탑으로 옮기는 행위를 move(n, 1 -> 3)하자.
원판이 4개라고 하면, 원판 3개를 1번째 탑에서 2번째 탑으로 옮기고 난 후(move(3), 1 -> 2), 마지막 원판을 3번째 탑으로 옮기고(원판 이동 출력, 1 -> 3), 2번째 탑에 있는 3개의 원반을  3번째 탑으로 옮긴다(move(3), 2 -> 3).

위 규칙을 이용해 정의한 원판을 옮기는 과정을 출력하는 함수는 다음과 같다.

/**
 * 원탑의 움직임을 출력하는 함수
 * 첫번째 출력 숫자는 출발 탑의 번호이고, 두번째 출력 숫자는 도착 탑의 번호
 * @param n 원판 개수
 * @param from 출발 탑의 번호
 * @param tmp 임시로 옮길 수 있는 탑의 번호
 * @param to 도착 탑의 번호
 */
void move_hanoi_tower(int n, int from, int tmp, int to)
{
    if(n == 1) printf("%d %d\n", from, to);
    else {
        move_hanoi_tower(n-1, from, to, tmp);
        printf("%d %d\n", from, to);
        move_hanoi_tower(n-1, tmp, from, to);
    }
}

 

C++로 구현한 전체 코드는 다음과 같다.
C에서 지원하는 함수로만 구현했기 때문에 C 컴파일도 가능하다.

#include <iostream>

using namespace std;

/**
 * 원판 옮긴 횟수 구하는 함수
 * @param n 원판 개수
 * @return 옮긴 횟수
 */
int count_hanoi_tower(int n)
{
    if(n == 1) return 1;
    else return 2 * count_hanoi_tower(n-1) + 1;
}

/**
 * 원탑의 움직임을 출력하는 함수
 * 첫번째 출력 숫자는 출발 탑의 번호이고, 두번째 출력 숫자는 도착 탑의 번호
 * @param n 원판 개수
 * @param from 출발 탑의 번호
 * @param tmp 임시로 옮길 수 있는 탑의 번호
 * @param to 도착 탑의 번호
 */
void move_hanoi_tower(int n, int from, int tmp, int to)
{
    if(n == 1) printf("%d %d\n", from, to);
    else {
        move_hanoi_tower(n-1, from, to, tmp);
        printf("%d %d\n", from, to);
        move_hanoi_tower(n-1, tmp, from, to);
    }
}

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

    // 원판 옮긴 횟수 출력
    printf("%d\n", count_hanoi_tower(N));
    // 옮기는 과정 출력
    move_hanoi_tower(N, 1, 2, 3);

    return 0;
}