JUNGOL 실력키우기 1161 : 하노이탑

하노이의 탑에 대한 전설은 아래와 같다.
고대 인도의 베나레스(현재 베트남의 하노이)​에 있는  한 사원에는 세상의 중심을 나타내는 큰 돔이 있고 그 안에 세 개의 다이아몬드 기둥이 동판 위에 세워져 있다. 기둥 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았다. 가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기까지 쌓여 있다. 이것은 신성한 브라흐마의 탑이다. 브라흐마의 지시에 따라 승려들은 모든 원판을 다른 기둥으로 옮기기 위해 밤낮 없이 차례로 제단에 올라 규칙에 따라 원판을 하나씩 옮긴다. 이 일이 끝날 때, 탑은 무너지고 세상은 종말을 맞이하게 된다.

 

기둥을 1, 2, 3 번으로 하고, N개의 원판이 작은 것부터 1, 2, 3, 4 … N이라고 할 때, 아래의 규칙에 따라 모든 원판을 3번 기둥으로 쌓기 위해 이동한다.
1. 한 번에 하나의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어서는 안 된다.

 

모든 원판이 1번 기둥에 순서대로 쌓여 있을 때, 3번 기둥으로 모두 이동하는 과정을 순서대로 출력하는 프로그램을 작성하시오.

 

1번 기둥에 쌓여 있는 원판의 개수 N(1≤N≤15)이 들어온다.

한 줄에 한 개의 원판을 이동하는 과정을 “원판번호 : 이동전 기둥번호 -> 이동후 기둥번호” 형식으로 모두 출력한다.

3	1 : 1 -> 3 2 : 1 -> 2 1 : 3 -> 2 3 : 1 -> 3 1 : 2 -> 1 2 : 2 -> 3 1 : 1 -> 3

---

재귀함수 문제의 대표 격으로 볼 수 있는 하노이 탑 문제가 등장했습니다.

이 문제는 재귀함수 내부에서 재귀함수 호출이 두번 일어나기에 처음 접했을 때는 상당히 어렵게 느낄 수 있습니다.

먼저 출력 예를 다시 써 보겠습니다.

1번 원판을 1번에서 2번 옆에있는 3번으로 이동

2번 원판을 1번에서 3번 옆에있는 2번으로 이동

1번 원판을 3번에서 1번 옆에있는 2번으로 이동

3번 원판을 1번에서 2번 옆에있는 3번으로 이동

1번 원판을 2번에서 3번 옆에있는 1번으로 이동

2번 원판을 2번에서 1번 옆에있는 3번으로 이동

1번 원판을 1번에서 2번 옆에있는 3번으로 이동

이것을 3번원판을 루트로 하는 트리 모양으로 바꾸면

위 트리를 해석하면 왼쪽으로 이동할 때 "옆에 있는"과 "으로 이동"을 바꾸고 오른쪽으로 이동할 때 "에서" 와 "옆에 있는"이 바뀝니다.

그리고 이것을 위 출력처럼 만들려면 중위 순회 방식으로 처리하면 됩니다.

그런데 실행하니 한 문제에 대해서 시간 초과가 발생하네요. 일반적으로 C++ 스타일의 IO가 오버헤딩이 크기 때문에 출력 스타일을 C 스타일로 변경해 다시 확인해 보겠습니다.

예상 했던 대로 성공했습니다. 거기에 실행 시간도 눈에 띄게 줄어들었군요. C++ 스타일의 입출력이 오버헤드가 큰 것 같으니 조심해야 할 것 같습니다.

#include <iostream>
 
using namespace std;
 
void Hanoi(int n, int from, int by, int to);
void PrintHanoi(int n, int from, int to);
 
int main()
{
    int n;
    cin >> n;
    
    // 하노이탑 수행
    // 1번에서 2번 옆에있는 3번으로 옮긴다.
    Hanoi(n, 1, 2, 3);
}
 
void Hanoi(int n, int from, int by, int to)
{
    // 종료 조건 정의
    if (n == 1)
    {
        PrintHanoi(n, from, to);
        return;
    }
 
    Hanoi(n - 1, from, to, by);
    PrintHanoi(n, from, to);
    Hanoi(n - 1, by, from, to);
}
 
// 중간 결과 출력
void PrintHanoi(int n, int from, int to)
{
    cout << n << " : " << from << " -> " << to << endl;
}

#include <iostream>
 
using namespace std;
 
void Hanoi(int n, int from, int by, int to);
void PrintHanoi(int n, int from, int to);
 
int main()
{
    int n;
    cin >> n;
    
    // 하노이탑 수행
    // 1번에서 2번 옆에있는 3번으로 옮긴다.
    Hanoi(n, 1, 2, 3);
}
 
void Hanoi(int n, int from, int by, int to)
{
    // 종료 조건 정의
    if (n == 1)
    {
        PrintHanoi(n, from, to);
        return;
    }
 
    Hanoi(n - 1, from, to, by);
    PrintHanoi(n, from, to);
    Hanoi(n - 1, by, from, to);
}
 
// 중간 결과 출력
void PrintHanoi(int n, int from, int to)
{
    printf("%d : %d -> %d\n", n, from, to);
}

JUNGOL) 문제은행) 실력키우기) 하노이탑