[프로그래머스] 하노이의 탑(C++)

문제 링크

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

프로그래머스

 

 

코드 풀이

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<vector<int>> answer;

// 원판 개수, 시작 기둥, 보조 기둥, 목적지 기둥
void Hanoi(int n, int start, int via, int dest)
{
    if (n == 1)
    {
        answer.push_back({ start, dest });
        return;
    }
    

    Hanoi(n - 1, start, dest, via);
    answer.push_back({ start, dest });
    Hanoi(n - 1, via, start, dest);
}

vector<vector<int>> solution(int n) 
{
    Hanoi(n, 0, 1, 2);

    return answer;
}

 

 

해결 방법

재귀 함수를 이용하여 해결했다. 출발 지점, 보조 지점, 목적지 지점을 정해두고, 현재 원판 보다 작은 원판을 보조 지점으로 옮긴 후 현재 원판을 목적지 지점으로 옮기고 다시 작은 원판을 위로 쌓아올리도록 하였다.