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

하노이의 탑

문제 링크

하노이의 탑

분석

하노이의 탑의 규칙은 다음과 같습니다.
한 번에 하나의 원판만 옮길 수 있습니다.
큰 원판이 작은 원판 위에 놓일 수 없습니다.
세 개의 기둥을 사용하여, 모든 원판을 시작 기둥에서 목표 기둥으로 옮겨야 합니다.

고전적인 재귀 문제로, 분할 정복 패턴으로 해결할 수 있는 입니다.
n - 1개의 원판을 보조 기둥으로 옮깁니다.
가장 큰 원판 1개를 목표 기둥인 3번 기둥으로 옮깁니다.
n - 1개의 원판을 보조 기둥에서 목표 기둥으로 옮깁니다.

문제의 기둥 개수는 3개입니다.
원판의 1번 기둥에 있는 원판 개수는 n개입니다.
1번 기둥의 모든 원판을 3번 기둥으로 옮길 때, 최소로 옮기는 횟수를 구해야합니다.

풀이

#include <vector>

using namespace std;

// 하노이 재귀 함수
// n: 옮겨야 하는 원판의 개수
// from: 현재 원판이 놓인 기둥 번호
// to: 옮겨야 할 목표 기둥 번호
// via: 보조 기둥 번호
// answer: 각 이동을 기록하는 2차원 벡터
void hanoi(int n, int from, int to, int via, vector<vector<int>>& answer)
{
    // 종료 조건으로 원판이 1개일 때 이동
    if (n == 1)
    {
        answer.push_back({from, to});
        return;    
    }
    
    // n - 1개 원판을 보조 기둥으로 이동한다.
    hanoi(n - 1, from, via, to, answer);
    
    // 가장 큰 원판을 목표 기둥으로 이동합니다.
    answer.push_back({from, to});
    
    hanoi(n - 1, via, to, from, answer);
}

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

성능 요약

시간 복잡도는 $O(2^n)$입니다.

• 하노이의 탑 재귀 호출 $O(2^n - 1) \approx O(2^n)$
• $O(2^n)$

공간 복잡도는 $O(2^n)$입니다.

• 재귀 호출 스택 $O(n)$
• 결과를 저장하는 벡터 vector<vector<int>> answer $O(2^n)$
• $O(n) + O(2^n)$

테스트 1 〉 통과 (0.02ms, 3.64MB)
테스트 2 〉 통과 (0.02ms, 4.13MB)
테스트 3 〉 통과 (0.04ms, 4.14MB)
테스트 4 〉 통과 (0.06ms, 4.15MB)
테스트 5 〉 통과 (0.17ms, 4.14MB)
테스트 6 〉 통과 (0.19ms, 4.14MB)
테스트 7 〉 통과 (0.57ms, 4MB)
테스트 8 〉 통과 (1.28ms, 4.24MB)
테스트 9 〉 통과 (1.70ms, 5MB)
테스트 10 〉 통과 (5.42ms, 6.61MB)
테스트 11 〉 통과 (6.37ms, 9.53MB)
테스트 12 〉 통과 (14.46ms, 15.7MB)
테스트 13 〉 통과 (23.54ms, 27.9MB)