프로그래머스 하노이의 탑

https://school.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이하의 자연수 입니다.

---

입출력 예

n result

2	[ [1,2], [1,3], [2,3] ]

---

문제를 풀어보면서 하노이탑 문제가 왜 레벨 2에 해당한는지 알 수 있었다,

풀어보고나면 간단하지만 접근 방법에 상당히 애를 먹었다.

결국 원리와 공식을 보고 문제에 어떻게 접근해야 할지 알게 되었다.

하노이 탑 문제를 해결하는 알고리즘은 재귀적인 방식을 사용한다. 이 알고리즘을 이해하기 위해서는 몇 가지 개념을 이해해야 한다.

1. 기본 규칙:
   • 원판을 옮기는 작업은 큰 원판 위에 작은 원판이 오지 않도록 한다.
   • 세 개의 기둥 중 하나에서 다른 기둥으로 옮길 때, 중간 기둥을 사용한다.
2. 재귀적 접근:
   • 하나의 원판을 제외하고 생각했을 때, 크기가 N-1인 원판들을 중간 기둥을 경유하여 목표 기둥으로 옮기는 문제로 변환된다.
   • 이렇게 크기가 작은 하위 문제를 해결한 후, 큰 원판을 목표 기둥으로 옮긴다.
3. 베이스 케이스:
   • 원판이 한 개일 경우, 바로 목표 기둥으로 옮기면 된다.

 

 

알고리즘

1. 만약 원판이 하나라면, 해당 원판을 출발지에서 목적지로 옮긴다.
2. 그렇지 않으면, (N-1)개의 원판을 중간 기둥으로 옮기고, 가장 큰 원판을 목적지로 옮긴 후, 나머지 원판들을 중간 기둥을 경유하여 목적지로 옮긴다.
3. 이를 재귀적으로 반복하여 모든 원판을 목적지로 옮긴다.

이러한 방식으로 재귀 호출을 사용하여 하노이 탑 문제를 해결할 수 있습니다.

 

 

코드

#include <string>
#include <vector>

using namespace std;

 vector<vector<int>> answer;

void hanoi(int n, int from, int to, int end){
    if(n==1){
        answer.push_back({from,to});
        return;
    }
    
    hanoi(n-1, from, end, to);
    answer.push_back({from,to});
    hanoi(n-1,end,to,from);
    
}

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