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

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

코딩테스트 연습 - 하노이의 탑

하노이의 탑

문제

하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.

1. 한 번에 하나의 원판만 옮길 수 있습니다.
2. 큰 원판이 작은 원판 위에 있어서는 안됩니다.

하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.

1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.

제한사항

• n은 15이하의 자연수 입니다.

 

풀이

입출력 예시

 

풀이

재귀 함수를 잘 이용한다면 쉽게 다가올 문제였다. 과정을 그대로 재귀함수화 시키면 되니까 말이다. 하노이의 탑을 진행하는 과정을 재귀함수로 구현이 용이하도록 풀어서 써보자.

 

1. n개의 원판이 주어졌다.

2. 1번의 원판을 2번으로 옮긴다.

3. 1번의 원판을 3번으로 옮긴다.

4. 2번의 원판을 1번으로 옮긴다.

5. 2-4의 과정을 반복한다.

 

예시로 주어진 문제의 과정을 그대로 구현하면 된다.

 

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> hanoi_tower(int n, int from, int mid, int to) {
    vector<vector<int>> result;
    
    if (n == 1) {
        return { { from, to } };
    }
    else {
        for (const auto& h : hanoi_tower(n - 1, from, to, mid)) {
            result.push_back(h);
        }
        result.push_back({ from, to });
        for (const auto& h : hanoi_tower(n - 1, mid, from, to)) {
            result.push_back(h);
        }
    }
    
    return result;
}

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