[프로그래머스] Lv.2 하노이의 탑 c++

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

프로그래머스

 

출처: wikiqedia

 

대표적인 재귀문제로 3개의 막대기둥 (A,B,C)가 주어지고 A의 막대기둥에 꽂힌 원판들을 B 막대기둥까지 옮기면 된다.

이때 조건이 주어진다.

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

A기둥에서 B기둥까지 모든 원판을 옮기는 최소 가짓수를 구해보자.

 

---

문제 이해 

처음에 이 문제를 봤을 때는 재귀의 개념이 쉽게 들어오지 않았다. 

원판을 재귀적으로 옮기는건 알겠는데 구체적으로 어떻게 옮기는 거지..? 

이걸 어떻게 코드로 구현하는가에서도 막혔다.

 

n=2 와 n=3일 때를 직접 그려보면 아래와 같다.

 

 

여기서 n=2 와 n=3을 비교해 보면 규칙이 나오는 걸 발견할 수 있다.

(1) A에 꽂힌 n-1개의 원판을 B로 전부 옮긴다.

(2) 남은 가장 큰 원판을 A에서 C로 옮긴다.

(3) B에 꽂힌 n-1개의 원판을 전부 C로 옮긴다.

 

n=2에서 원판을 A에서 C로 옮기는데 3가지 단계를 거친다.

n=3 역시 세가지 과정을 반복하여 원판을 옮긴다.

3단계를 보면 1번규칙이 적용되고, 4단계는 2번 규칙이 적용된다.

이후 다시 5~7단계에서는 3번 규칙에 따라 B에 있던 n-1개의 원판을 C로 옮기는 과정을 반복하게 된다.

이런 방식으로 규칙을 이해하면, n이 몇이든 동일한 구조로 문제를 해결할 수 있다는 걸 알 수 있다.

결국 하노이 탑 문제는 크기가 다른 원판들이 “어떻게 단계적으로 옮겨지는가”를 규칙적으로 나누어 생각하는 게 핵심이다.

 

 

풀이 방법

앞서 말했듯이 재귀를 사용하면 된다.

move함수를 따로 만들어 이동 경로를 저장하고, hanoi()함수를 만들어 원판을 옮기는 재귀적인 과정을 구현했다.

 

hanoi() 함수는 크게 세 단계로 나뉜다:

1. Step 1:  n-1 개의 원판을 보조 기둥(sub)으로 옮긴다. 이 과정은 hanoi()를 다시 호출해 재귀적으로 수행한다.
2. Step 2: 가장 큰 원판( n )을 출발 기둥(start)에서 도착 기둥(end)으로 직접 옮긴다. 이때 move() 함수를 사용해 이동을 기록한다.
3. Step 3: 보조 기둥(sub)에 있던  n-1 개의 원판을 다시 도착 기둥(end)으로 옮긴다. 이 과정 역시 hanoi()를 다시 호출해 재귀적으로 수행한다.

 

풀이 코드

#include <string>
#include <vector>

using namespace std;
vector<vector<int>> moves;

void move(int disk, int start, int end){
    moves.push_back({start,end});
}

void hanoi(int n, int start, int end, int sub){
    //원판이 한개 뿐이라면 start에서 end로 옮긴다(A->C) 기저사례
    if(n==1){
        move(1, start, end);
        return;
    }
    //step 1 : n-1개의 원판을 end기둥을 경유하여 start부터 sub까지 옮긴다 (A->B)
    hanoi(n-1, start, sub, end);
    //step 2 : start위치에서 end위치로 맨 아래 원판을 옮긴다. (A->C)
    move(n, start, end);
    //step 3 : n-1개의 원판을 sub에서 end까지 start기둥을 경유하여 옮긴다.(B->C)
    hanoi(n-1, sub, end, start);
}

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

 

 

 

 

내가 도움이 많이 된 블로그도 참조할 테니 보면 좋을 것 같다.

https://shoark7.github.io/programming/algorithm/tower-of-hanoi