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

---

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

#include <string>
#include <vector>
#include <stack>
#include <iostream>

using namespace std;

vector<vector<int>> moveDisk(int n, int from, int to, int temp){
    vector<vector<int>> moves;
    
    if(n == 1){
        moves.push_back({from, to});
        
        return moves;
    }
    
    vector<vector<int>> moves1 = moveDisk(n - 1, from, temp, to);
    moves.insert(moves.end(), moves1.begin(), moves1.end());
    
    moves.push_back({from, to});
    
    vector<vector<int>> moves2 = moveDisk(n - 1, temp, to, from);
    moves.insert(moves.end(), moves2.begin(), moves2.end());
    
    return moves;
}

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

---

📝 풀이

이 문제는 재귀 함수를 통하여 풀었습니다.

기저 조건은 n = 1인 경우 원판을 from에서 to로 옮기면 됩니다.

이후 세 단계로 나누어 수행됩니다.

1. n-1개의 원판을 from에서 temp로 옮깁니다.

2. 가장 큰 n번의 원판을 from에서 to로 옮깁니다.

3. n-1개의 원판을 temp에서 to로 옮깁니다.

이 모든 이동 경로를 담은 moves를 return 합니다.