문제

3개의 지팡이가 있고, 순서대로 1, 2, 3번 솟대라고 하자.
n개의 디스크들은 모두 1번 솟대에 꽂혀 있고, 모두 3번 솟대로 옮겨야 한다.
이 때 자기보다 큰 디스크는 절대로 위에 올릴 수 없다

이 때 맨 처음부터 n개의 디스크들을 옮기는 순서를 return하는 코드를 짜라.

---

접근

하노이 탑의 recursive 구조를 정의하면 9할 이상 끝이다.

n개의 디스크를 1번에서 3번으로 옮기려면 아래와 같은 작업이 필요하다.

1. (1 ~ n-1)번째 디스크들을 2번에 옮긴다.
	1.1 (1 ~ n-2)번째 디스크들을 3번에 옮긴다.
		1.1.1(1 ~ n-3)번째 디스크들을 2번에 옮긴다. ...
    1.2 n-1번째 디스크를 2번에 옮긴다.
    1.3 (1 ~ n-2)번째 디스크들을 2번에 옮긴다.
2. n 번째 디스크를 3번에 옮긴다.
	....
3. (1 ~ n-1)번째 디스크들을 3번에 옮긴다.
	...

계속해서 반복되는 패턴이 나오고, 이 패턴을 recursive하게 표현할 수 있다.

가령 1~X번째까지 순서대로 쌓여있는 디스크가 있을 때 이것을 옮기는 방법을 다음과 같이 표현할 수 있다.
디스크가 현재 있는 솟대의 위치를 current, 도착해야 하는 솟대는 destination, 중간 경유지를 via라고 할 때:

1. (1 ~ X-1) 번째 디스크들을 via에 둔다.
2. X번째 디스크를 destination에 둔다.
3. (1 ~ X-1) 번째 디스크들을 destination으로 옮긴다.

순으로 표현할 수 있고, 이것을 hanoi(X, current, destination) 라는 함수로 만든다.

1번을 수행하기 위해선 hanoi(X-1, current, via) 를 하면 되고, 3번은 hanoi(X-1, via, destination) 이다.

이제 구조화를 마쳤으니, 하나의 디스크가 옮겨지는 순간에 current와 destination을 출력하게 하면 끝!

---

코드 구현

#include <string>
#include <vector>

using namespace std;
vector<vector<int> > answer;

void hanoi(int n, int current, int destination) {
    int via = 0;
    vector<int> result;

    if(n == 1) {
        result.push_back(current);
        result.push_back(destination);
        answer.push_back(result);

        return;
    }

    for(int i = 1; i <= 3; ++i) {
        if(i != current && i != destination) { 
            via = i;
            break;
        }
    }

    hanoi(n-1, current, via);
    
    
    result.push_back(current);
    result.push_back(destination);
    answer.push_back(result);

    hanoi(n-1, via, destination);

    return;
}

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

---

만약 더 나은 풀이나 잘못된 로직이 있다면 댓글을 통해 알려주시면 감사하겠습니다 :)