# 프로그래머스 : 하노이의 탑 (Level 5)

[문제]
하노이의 탑은 대표적인 퍼즐의 일종입니다. 세 개의 기둥이 있고 맨 왼쪽의 기둥에는 원판의 크기 순서대로 N개가 쌓여 있습니다. 
이렇게 쌓여 있는 원판을 가장 오른쪽 기둥으로 모두 옮겨야 합니다.
단, 한 번에 원판을 하나씩 이동시킬 수 있고, 큰 원판을 작은 원판 위에 쌓을 수 없습니다.
N개의 원판은 총 2N -1 번의 과정을 거쳐 이동할 수 있습니다. 하지만 어떠한 과정으로 원판을 옮겨야 2N -1 번만에 옮길 수 있는지는 아직 모릅니다. 원판이 N개 있을 때, Hanoi 함수에서 어떠한 과정으로 2N -1 번만에 옮길 수 있는지 과정을 리턴하세요. 
리턴값의 표기 방법은 다음과 같습니다.
  • 3개의 기둥은 순서대로 각각 1, 2, 3번으로 표기합니다. 
  • 원판을 기둥1에서 기둥3으로 이동했다면 [1, 3]으로 표기합니다.
  • 원판을 기둥3에서 기둥1로 이동했다면 [3, 1]로 표기합니다.
이러한 이동 순서를 담는 배열을 리턴하면 됩니다. 예를들어 N이 2라면 아래 그림과 같이 옮길 수 있으므로, 리턴값은 [ [1,2], [1,3], [2,3] ]입니다.

[풀이]


 결론부터 말하면
'완벽하게 풀지 못했다' 

 우선 하노이의 탑은 풀었는데, 그 내용을 출력하는 방법을 몰라서..
(이 부분은 알게 되면 추후 포스팅 하도록 하겠다)










위 그림이 하노이의 탑을 나타내는데, 아래의 규칙이 존재한다.

  • 각 원반은 세 개의 탑 중 어느 한 곳에라도 꽂혀있어야 한다.
  • 각 원반은 한번에 한 개씩 이동할 수 있다.
  • 각 원반은 자기보다 작은 원반 위에 올라갈 수 없다.

이동 방법은 위의 문제에 나온 예시를 보면 어느정도 감이 올 것이라 생각하고,
결국 n개의 원반을 A에서 C까지 옮기려면
  1. n-1개의 원반을 A에서 B까지 옮기고
  2. n번째 원반(가장 밑에 있어야 하는 녀석)을 C로 옮기고
  3. B에 있는 n-1개의 원반을 C로 옮긴다.
n이 몇개가 되던 결국 위 3개의 순서를 무조건 거치게 된다.
이를 통해 n개의 원반을 A에서 C까지 옮길 수 있는 최소한의 횟수는 2^n -1 개가 된다.

소스 코드를 통해 들여다보면 다음과 같다.

void move(int num, int from, int by, int to) {
    if(num == 1) {
        //print(from, to);
    }
    else {
        move(num-1, from, to, by);
        //print(from, to);
        move(num-1, by, from, to);
    }
}

주석처리로 한 print는 어디에서 어디까지 이동하는건지를 출력하는 함수인데 밑에 써놓겠다.
(우선 중요한 내용은 아니기 때문에!)
from은 시작점, by는 중간, to는 종착점이라고 하자.
결국 A->C로 이동한다고 할 때, from은 A, by는 B, to는 C가 된다.

move(num-1, from, to, by) : A에서 B로 num-1개를 옮기는데, C를 거쳐라(이용해라)
move(num-1, by, from, to) : B에서 C로 num-1개를 옮기는데, A를 거쳐라(이용해라)

print 함수는 마음대로 작성하면 되는데, 나 같은 경우 다음과 같이 작성하였다.

void print(int from, int to) {
    cout<<"["<<from<<", "<<to<<"]";
}

이런식으로 하면, 이동경로가 출력되는 것을 확인할 수 있다.

참고로 말하면, 처음 시작은 당연히 move(갯수, 1, 2, 3)이 되어야한다.
여기서 1은 A, 2는 B, 3은 C가 되는것도 당연하다.

[추가적인 풀이 : 해결!]


 출력방법은 간단했다.
위에서 말한 리턴 값 [[1,2], [1,3], [2,3]] 은 2차원 벡터로 표현하면 되는 문제였다.
결국 2차원 벡터 : vector<vector<int>> answer로 할 때,
1차원 벡터로 vector<int> temp_answer로 두고 1,2를 temp_answer에 push_back한 다음
2차원 벡터 answer에 push_back 하라는 의미였다.

 수정된 코드를 다시 올린다.
vector<vector<int> > answer;

void move(vector<vector<int>>&answer,int num,int from,int by,int to)
{
    vector<int> result;
    if(num == 1) {
        result.push_back(from);
        result.push_back(to);
        answer.push_back(result);
    }
    else {
        move(answer, num-1, from, to, by);
        result.push_back(from);
        result.push_back(to);
        answer.push_back(result);
        move(answer, num-1, by, from, to);
    }
}

vector<vector<int> > hanoi(int no)
{
    move(answer, no, 1,2,3);
    return answer;

}

댓글

댓글 쓰기