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

문제 설명

하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.

1. 한 번에 하나의 원판만 옮길 수 있습니다.
2. 큰 원판이 작은 원판 위에 있어서는 안 됩니다.

하노이 탑의 세 개의 기둥을 왼쪽부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.

1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return 하는 solution를 완성해주세요.

 

제한 조건

• n은 15 이하의 자연수입니다.

 

입출력 예

n	result
2	[ [1,2], [1,3], [2,3] ]

 

 

코드

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> answer;

// n번 원판을 from 기둥에서 to 기둥으로 옮김
void hanoi(int n, int from, int tmp, int to)
{
    vector<int> v;
    
    v.push_back(from);
    v.push_back(to);
    if (n == 1)
    {
        answer.push_back(v);
        return;
    }
    hanoi(n - 1, from, to, tmp);
    answer.push_back(v);
    hanoi(n - 1, tmp, from, to);
}

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

 

1번 기둥에 있는 n개의 원판을 3번 기둥으로 옮기는 것이 목표이기 때문에 1번을 출발지, 2번을 경유지, 3번을 목적지로 하여 hanoi() 함수를 호출한다. 벡터 v는 from에서 to로 원판 하나를 옮긴 것을 의미하며 answer의 원소로 저장된다. 다음은 n이 3일 때의 수행 과정이다.

 

링크

코딩테스트 연습 - 하노이의 탑

inbdni/Programmers