[프로그래머스 lv2] 하노이의 탑 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

n개의 원판들을 1번 기둥에서 3번 기둥으로 옮기는 하노이 문제이다.

처음 하노이 문제를 보는 사람이라면 규칙을 찾아서 절차적으로 해결하려고 노력하게 된다.

하지만 절차적으로 생각하면 할 수록 더욱 미궁 속으로 빠지게 되고...

이 문제는 재귀의 가장 대표적인 유형으로 재귀적 사고를 통해 해결해야 한다.

 

func(int n, int f, int t)는 n개의 원판을 f 기둥에서 t 기둥으로 옮길 때 필요한 이동 방법을 리턴한다.

원판을 옮길 때 큰 원판은 절대 작은 원판보다 먼저 움직일 수 없다.

따라서, n개의 원판을 f에서 t로 옮기려면, n-1개까지의 원판을 f, t가 아닌 다른 기둥에 옮겨놓고 가장 마지막에 있는 n번째 원판을 f에서 t로 이동시켜야 한다. 이후, n-1개의 원판을 다시 t 기둥으로 옮기면 모든 원판을 f에서 t로 옮길 수 있다.

 

이 과정을 함수로 써보면,

func(int n , int f, int t)는 결국

func(n-1, f, (f와 t가 아닌 기둥)) + [f, t](n번째 원판의 이동) + func(n-1, (f와 t가 아닌 기둥), t) 이 된다.

세 기둥의 합은 1 + 2 + 3 = 6 이므로, f와 t가 아닌 기둥은 6-f-t 로 구할 수 있다.

 

재귀함수는 종료 조건이 필요하므로 n == 1일 때 [f, t] 를 그대로 리턴해주면 하노이 함수가 완성된다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cctype>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

vector<vector<int>> func(int n, int f, int t) {

    if (n == 1) return {{f, t}};
    vector<vector<int>> v1 = func(n-1, f, 6-f-t);
    v1.push_back({f, t});
    vector<vector<int>> v2 = func(n-1, 6-f-t, t);
    for (auto x : v2) v1.push_back(x);
    return v1;
}

vector<vector<int>> solution(int n) {
    return func(n, 1, 3);
}