Programmers - 하노이의 탑

---

title: Programmers - 하노이의 탑
date: 2022-07-07
tags:

• Algorithm
• Recursion

---

https://school.programmers.co.kr/learn/courses/30/lessons/12946

문제 요약

하노이의 탑 문제이다. n개의 원판이 주어지며, 1번 기둥에 쌓여있다.
모든 원판을 3번 기둥에 최소 횟수로 옮겨야 하며, 과정을 vector에 넣어 return한다.

문제 풀이

최소 횟수는 바로 구할 수 있으나, 과정을 기록해야 한다는 것이 꽤 거슬렸다.
하노이의 탑은 원판의 움직임에 패턴이 존재하며, 원판의 개수와 위치에 따라 과정이 너무 동적으로 변화하여 DP는 사용하기 어렵다고 판단하였다.
결국 성능을 다소 포기하더라도 가장 구현하기 쉬운 재귀 함수로 구현하였다.
1번 기둥에서 3번 기둥으로 n개만큼 옮기는 재귀 함수를 호출한다.
1 == n 이라면 바로 옮기며, 그렇지 않을 경우 n-1개를 남은 기둥으로, 1개를 target 기둥으로, 나머지 n-1개를 target 기둥으로 옮기면 된다.
로직 자체는 매우 쉬우나 재귀 함수이기에 성능 측면에서 매우 아쉽다.

프로그램

#include <vector>
#include <stack>

using std :: vector ;
using std :: stack ;

vector < vector < int > > vAnswer ;
stack < int > vStack [ 3 ] ;

void recursiveHanoi ( int iCurrent , int iCount , int iTarget , int iEmpty )
{
    if ( 1 == iCount )
    {
        int iSize = vStack [ iCurrent ].top () ;
        vStack [ iCurrent ].pop () ;
        vStack [ iTarget ].emplace ( iSize ) ;

        vAnswer.push_back ( { iCurrent + 1 , iTarget + 1 } ) ;

        return ;
    }

    recursiveHanoi ( iCurrent , iCount - 1 , iEmpty , iTarget ) ;
    recursiveHanoi ( iCurrent , 1 , iTarget , iEmpty ) ;
    recursiveHanoi ( iEmpty , iCount - 1 , iTarget , iCurrent ) ;
}

vector < vector < int > > solution ( int n )
{
    for ( int i = n ; i > 0 ; --i )
    {
        vStack [ 0 ].emplace ( i ) ;
    }


    recursiveHanoi ( 0 , n , 2 , 1 ) ;

    return vAnswer ;
}