[Coding Test] 하노이의 탑/c++

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

프로그래머스

 

하노이의 탑은 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있다.

퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있고 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓아야 한다.

 

조건은 아래와 같다.

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

1번에 있는 원판들을 3번으로 옮겨야 한다.

 

큰 원판이 제일 밑으로 가도록 쌓아야 하기 때문에 제일 밑의 원판을 먼저 3번으로 옮겨야 한다.

그런데 제일 밑의 원판을 옮기기 위해서는 위에 있는 원판들을 2번으로 옮겨야 한다.

 

정리하면 다음과 같다.

1. 가장 밑에 있는 원판을 제외하고 남는 기둥으로 옮긴다.

2. 가장 밑에 있는 원판을 목표 기둥으로 옮긴다.

 

이 과정을 반복하고 나면 남은 기둥들도 모두 동일하게 옮길 수 있으니 위의 과정을 반복하면 된다.

 

#include <vector>
using namespace std;

void hanoi(int n, int origin, int target, int left, vector<vector<int>>* answer)
{
    //n이 0이면 옮길 원판이 없다는 뜻이다.
    if(n == 0) return; 

    //가장 밑의 원판을 제외하고 남는 기둥으로 옮긴다.
    //그 원판들을 옮기기는 과정 또한 같은 과정을 거친다.
    hanoi(n-1, origin, left, target, answer);

    //가장 밑의 원판을 목표 기둥으로 옮긴다.
    vector<int> v1;
    v1.push_back(origin);
    v1.push_back(target);
    (*answer).push_back(v1);
    
    //남는 기둥으로 옮겼던 원판들에 대해서 위의 과정을 반복한다.
    hanoi(n-1, left, target, origin, answer);
}

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