[프로그래머스] 하노이의 탑 / 재귀 / C++ 풀이

문제

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

프로그래머스

 

C++ 풀이

#include <string>
#include <vector>
using namespace std;

vector<vector<int>> gAnswer;

void hanoi(int n, int src, int path, int dst)
{
    if(n == 0) return;
    hanoi(n - 1, src, dst, path);
    gAnswer.push_back({src, dst});
    hanoi(n - 1, path, src, dst);
}

vector<vector<int>> solution(int n) {
    hanoi(n, 1,2,3);
    return gAnswer;
}

제일 아래에 있는 n번 링을 src에서 dst로 옮겨야 한다면, n아래에 있는 (n-1)까지의 링을 dst가 아닌 곳으로 옮겨야 한다.

원래 있는 위치를 src, 옮겨야 하는 위치를 dst, 그 둘도 아닌 곳을 path라고 하자.

hanoi(n - 1, src, dst, path); 는 1부터 n-1까지의 링을 path로 옮긴다.

 

이것이 수행된 이후에는 n번 링을 src에서 dst로 옮길 수 있다. 이렇게 path로 옮겨진 n-1개의 링을 다시

dst 위치로 옮겨야 한다. 이는 hanoi(n - 1, path, src, dst);가 수행한다.