# 11729. 하노이 탑 이동 순서

관련 알고리즘 : 재귀

 

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

11729번: 하노이 탑 이동 순서

 

---

 

문제 풀이

문제의 조건을 보면, 

1. 한 번에 한 개의 원판만 이동 가능

2. 쌓아 놓은 원판의 크기는 항상 아래로 갈수록 커져야 함

을 만족 시켜야 한다.

 

위 두 조건을 만족하면서 n개의 원판을 1번에서 3번 장대로 이동시키기 위해서 그 흐름을 생각해 보았다.

 

• n번 원판은 3번 장대 위에 있어야 나머지 (n-1)개의 원판들이 순서대로 n번 원판 위로 이동 가능
• (n-1)개의 원판들은 순서대로 2번 장대로 이동하고 나서야 다시 1번 장대를 거쳐서 3번 장대로 이동 가능

1 ~ (n-1) 원판 => 2번 장대로 이동  //  n번 원판 => 3번 장대로 이동

1 ~ (n-2)번 원판 => 1번 장대로 이동  //  (n-1)번 원판 => 3번 장대로 이동

1 ~ (n-3) 원판 => 2번 장대로 이동  //  n번 원판 => 3번 장대로 이동

흐름을 정리해 보면, 3번째 사진 속 (n-2)번 원판을 옮길 때 1번째 사진의  n번 원판을 3번 장대로 옮길 때처럼 나머지 원판들이 2번 원판을 거쳐간다는 것을 알 수 있다. 

즉, 짝수번마다 앞의 2개의 원판들이 이동했던 흐름들을 그대로 따라간다. 

이를 이용하여 hanoi(num, start, to, end) 형태의 함수를 사용해 재귀로 풀어나가면 문제를 해결할 수 있다.

 

또, 문제를 보면 최소 이동 횟수를 먼저 출력해야 하는데, 

위에서 생각했던 것들을 토대로 이동 횟수를 생각해 보면

• 제일 큰 원판은 3번 장대로 한번 옮김
• 제일 큰 원판을 제외한 나머지 원판들은 1번이나 2번 장대를 거쳐 각 2번씩 이동

따라서, ( (n-1)개의 원판이 이동한 횟수 * 2 ) + 1 ) 이 되는데, 이를 정리해보면 2^n-1 임을 알 수 있다.

 

---

C++ 코드

#include <iostream>

using namespace std;

void hanoi(int num, int start, int to, int end)
{
    if(num==1)
        cout << start << " " << end << "\n"; // 원판이 1개일 경우, 1번 장대에서 3번 장대로 이동
    else // 원판이 1개보다 많을 경우
    {
        // (n-1)개의 원판을 2번 장대(to)로 옮겨야 하므로 1번 장대에서 시작하여 3번 장대를 거쳐 2번 장대로 이동
        hanoi(num-1, start, end, to);
        cout << start << " " << end << "\n"; // 마지막 원판 3번 장대로 이동
        // (n-1)개의 원판들이 2번 장대로 옮겨진 상태에서 최종 목적지인 3번 장대로 이동하여야 하므로 1번 장대를 거쳐 3번 장대로 이동
        hanoi(num-1, to, start, end);
    }
}

int main()
{
    int n; // 원반 갯수
    cin >> n;
    cout << (1<<n)-1 <<"\n"; // 최소 이동 횟수 2^n-1 출력
    hanoi(n, 1, 2, 3);
    return 0;
}