[프로그래머스 Level2] 하노이의 탑

📝 하노이의 탑

문제 설명

하노이의 탑

해결 방법

유명한 재귀함수 문제라 재귀함수로 해결했으나, 비재귀 방법도 궁금해서 한번 찾아보았다.
3개의 기둥이 있으므로 from(출발 기둥), to(도착 기둥), by(임시 기둥), n(원판의 개수) 매개변수를 선언한다. answer를 출력해야 하므로 2차원 벡터도 같이 매개변수로 선언한다.
n개의 원판을 옮기 때, 큰 원판이 작은 원판 위에 있어서는 안된다.
원판이 1개일 경우 from 기둥에서 to 기둥으로 바로 옮기면 되므로 재귀함수의 기저 조건(종료 조건)을 설정한다.
원판이 2개인 경우 1개의 원판을 by 기둥으로 옮기고 가장 큰 원판을 to 기둥으로 옮긴 다음, by 기둥에 있던 원판을 to 기둥으로 옮긴다.
원판이 3개인 경우 2개의 원판을 by 기둥으로 옮기고 가장 큰 원판을 to 기둥으로 옮긴 다음, by 기둥에 있던 2개의 원판을 to 기둥으로 옮긴다.
일반화하면, 원판이 n개인 경우 n - 1 개의 원판을 by 기둥으로 옮기고 가장 큰 원판을 to 기둥으로 옮긴 다음, by 기둥에 있던 n - 1 개의 원판을 to 기둥으로 옮기면 된다.
이를 코드로 나타내면 재귀함수를 이용한 풀이와 같다.

// 재귀구조
hanoi(3, 1, 3, 2)
	hanoi(2, 1, 2, 3)
    	hanoi(1, 1, 3, 2)
        	[1, 3]
        [1, 2]
        hanoi(1, 3, 2, 1)
        	[3, 2]
    [1, 3]
    hanoi(2, 2, 3, 1)
    	hanoi(1, 2, 1, 3)
        	[2, 1]
        [2, 3]
        hanoi(1, 1, 3, 2)
        	[1, 3]
[1, 3] -> [1, 2] -> [3, 2] -> [1, 3] -> [2, 1] -> [2, 3] -> [1, 3]

💻소스코드

재귀함수를 이용한 풀이

#include <string>
#include <vector>

using namespace std;

void hanoi(vector<vector<int>>& v, int n, int from, int to, int by) {
	if (n == 1) {   // 종료 조건
        v.push_back({from, to});
    }
    else {
    	hanoi(v, n - 1, from, by, to);
        v.push_back({from, to});
        hanoi(v, n - 1, by, to, from);
    }
}

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