[알고리즘] 백준 11729번 "하노이 탑 이동 순서" (C/C++) - Don 임베디드

문제요약:

세 개의 장대가 있고 첫 번째 장대에 서로 지름이 다른 N개의 원판이 쌓여있다.

각 원판은 지름이 큰 순서대로 쌓여있다.

현 순서와 동일하게 세 번째 장대로 옮기려고 하는데,

다음 규칙을 지켜야 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.

2. 쌓아 높은 원판은 항상 위의 것이 아래보다 작아야만 한다.

이 작업을 하면서 필요한 각 원판의 총 이동 횟수와, 

원판이 이동한 경로를 출력하라.

 

제약:

시간 제한 1초, 메모리 256MB

첫 장대에 쌓인 원판 N개에 대하여 1<= N <= 20.

 

출력:

첫째 줄에는 총 원판을 이동시킨 횟수를 출력한다.

두번째 줄 부터는 수행 과정을 출력한다.

K 개의 줄에 걸쳐 시작 타워의 번호(A), 빈칸( ), 목적지 타워의 번호(B)를 출력한다.

이는 A의 가장 위에 있는 원판을 B로 옮긴다는 뜻이다.

 

예제 1 입력.	예제 1 출력.
1	1 1 3
예제 2 입력.	예제 2 출력.
3	7 1 3 1 2 3 2 1 3 2 1 2 3 1 3

 

 

정답코드:

 

#include <iostream>
#include <vector>
 
using namespace std;
 
// 총 움직인 횟수를 저장할 global 변수 선언.
int gnMovedCount;
 
class MoveHistory
{
public:
    int nStart;
    int nDest;
    MoveHistory(int nStart, int nDest) : nStart(nStart), nDest(nDest) {}
};
 
// 총 움직인 횟수를 먼저 출력해야 하기 때문에,
// MoveHisoty를 저장해 놓을 데이터가 필요.
vector <MoveHistory> v;
 
void moveChunk(int nStart, int nDest, int nNumOfBlocks)
{
    int nLayover = ((nStart + 1) % 3) + 1;
 
    if (nLayover == nDest)
    {
        // Start도 아니고 Dest도 아닌 Tower 번호를 찾는다.
        // "Layover"는 경유지라는 뜻.
        nLayover = ((nDest + 1) % 3) + 1;
    }
    if (nNumOfBlocks == 1)
    {
        // 블럭이 1이면 Start에서 Dest로 바로 움직일 수 있다.
        v.push_back(MoveHistory(nStart, nDest));
        gnMovedCount++;
    }
    else if (nNumOfBlocks <= 20)
    {
        // 블럭이 N일때,
        /*****************************/
        /*    1         X        X   */
        /*    2         X        X   */
        /*    3         X        X   */
        /* (Start)  (Layover)  (Dest)*/
        /*****************************/
        // Step1. 위에 있던 N-1 개의 블럭들을 경유지 Tower로 옮겨놓는다.
        /*****************************/
        /*    X         X        X   */
        /*    X         1        X   */
        /*    3         2        X   */
        /* (Start)  (Layover)  (Dest)*/
        /*****************************/
        moveChunk(nStart, nLayover, nNumOfBlocks - 1);
        // Step2. N번 블럭을 목적지 Dest로 옮긴다.
        /*****************************/
        /*    X         X        X   */
        /*    X         1        X   */
        /*    X         2        3   */
        /* (Start)  (Layover)  (Dest)*/
        /*****************************/
        v.push_back(MoveHistory(nStart, nDest));
        gnMovedCount++;
        // Step 3. N-1 개의 블럭들을 목적지 Dest로 옮긴다.
        /*****************************/
        /*    X         X        1   */
        /*    X         X        2   */
        /*    X         X        3   */
        /* (Start)  (Layover)  (Dest)*/
        /*****************************/
        moveChunk(nLayover, nDest, nNumOfBlocks - 1);
    }
    else
    {
        // Out of Range
        cout << "N is out of range!!!!" << '\n';
        return;
    }
}
int main()
{
    int N;
 
    // 문제 입력.
    cin >> N;
 
    // 총 Move 횟수 초기화.
    gnMovedCount = 0;
 
    // Tower 1에서 Tower 3으로 N개의 블럭을 움직이는 재귀 함수 호출.
    moveChunk(1, 3, N);
 
    // 총 이동한 횟수 출력.
    cout << gnMovedCount << '\n';
 
    // Move History를 순회할 iterator를 선언.
    vector <MoveHistory>::iterator iter;
 
    // vector에 저장돼있는 MoveHistory를 모두 출력.
    for (iter = v.begin(); iter != v.end(); iter++)
    {
        cout << (iter->nStart) << ' ' << (iter->nDest) << '\n';
    }
 
    return 0;
}

 

원본 링크: https://www.acmicpc.net/problem/11729