c++ 하노이의 탑, 재귀함수, 백준 11729

 

 

1. 하노이의 탑

 

재귀함수 문제로 가장 유명하면서도, 재귀함수에 대한 이해를 위해 아주 기초적인 문제이다.

 

How to Solve the Tower of Hanoi Problem - An Illustrated Algorithm Guide (freecodecamp.org)

 

 

하노이의 탑은 1883년 프랑스 수학자 에두아르 뤼카가 제시한 문제로

 

그림과 같이, 주어진 크기가 다른 N개의 원판과 3개의 막대(A,B,C)에 대하여 

A의 모든 원판을 C로 옮기는 것인데 조건이 있다.

 

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

문제는 보통 이같은 조건을 지키며 A에서 C로 모든 원판을 옮기는 최소 실행수 또는 그 순서를 요구한다.

 

해결에 들어가기 전에

하노이의 탑 (Tower of Hanoi) - 플래시게임 | 와플래시 게임 아카이브 (tistory.com)

하노이의 탑 (Tower of Hanoi)

 

여기서 한번 실제로 플레이해보고 어느정도 감을 익힌다면 접근하는데 쉬워질 것 이다.

 

 

 

 

2. 재귀적 접근

 

11729번: 하노이 탑 이동 순서 (acmicpc.net)

11729번: 하노이 탑 이동 순서

 

나는 이 문제처럼, 원판의 이동 순서과 최소 이동횟수를 구하고 싶다.

 

각 원판을 그 크기에 따라 1,2,3...N으로, 막대를 A,B,C로 생각하자.

 

물론 우리는 이를 재귀함수로 해결해야한다는 것을 알고있지만, 그 전에 왜 재귀로 접근해야하는지 생각해보자.

 

N = 1일때, 원판1을 A->C로 옮긴다. (총 1번)

N = 2일때, 원판1을 A->B로, 원판2를 A->C로, 원판1을 B->C로 옮긴다. (총 3번)

N = 3일때는 그림으로 살펴보자

Program for Tower of Hanoi Algorithm - GeeksforGeeks

 

주목해야할 것은 3번 과정인데, 3번 원판을 옮기기 위해 1번과 2번 원판을 B막대(경유지)로 옮겼다.

 

잘 생각해보자, 우리는 N=2일때 총 3번의 과정을 거쳐 1번과 2번 원판을 A에서 C로 옮겼다.

 

N=3일 때, 7번의 과정 중 첫 3번째 과정은 1번과 2번 원판을 A에서 B로 옮기는 과정이었다.

 

즉, N=3일때 문제 해결 과정은 N=2일때 과정을 포함할 수 있다는 것이다.

 

또한 위 그림에서, 5번째~7번째 역시 B막대에 있는 두 원판을 C로 옮기는 과정인데 이 역시 N=2일때의 과정과 동일하다.

 

결국 hanoi(N)에 hanoi(N-1)이 포함된다는 의미이고, 따라서 이 문제를 재귀적으로 접근할 수 있다는 것이다.

 

 

 

hanoi(N)에 두번의 hanoi(N-1)이 포함된다는 것은 알았지만

 

사실 이 두번의 hanoi(N-1)이 정확히 N=2일때의 과정과 똑같지는 않았다.

 

각 과정의 출발지와 도착지, 그리고 경유지로 사용하는 막대가 모두 달랐다.

 

이들의 정보를 정의할 필요가 있다.

 

따라서 hanoi(N)을, N개 원판을 via를 거쳐 start에서 dest로 옮긴다는 의미의

 

hanoi(N,start,dest,via) 로 정의할 수 있다.

 

 

 

이를 이용해 다시 한번 hanoi(3,A,C,B) 를 분해해보자.

 

이미 위 그림을 통해 두번의 hanoi(2)가 포함된다는 것은 알았다.

 

각 과정을 hanoi(N,start,dest,via) 형태로 표현하자.

1-3번째 : hanoi(2,A,B,C)
5-6번째 : hanoi(2,B,C,A)
4번째 : 경유지 없이 바로 3번째 원판을 A에서 C로 이동 = move(3,A,B)

 

 

 

3. 구현

 

재귀 함수 작성에는 규칙이 있다.

 

1) Base Case : 반복이 멈추는 조건

재귀를 돌면서 더 이상 문제를 하위단계로 분해할 수 없는 멈춤 조건이 정의되어야 한다.

 

2) Recursion : 반복

함수 자기 자신을 호출하며 재귀적으로 반복되는 과정이다.

 

 

 

이에 따라 하노이 탑 문제를 정의해보자.

 

Base case는 N=1일때이다. N=1 일땐 경유지 없이 그저 start에서 dest로 원판을 옮기기만 하면 된다.

 

Recursion은 이미 정의했다. hanoi(N-1,start,dest,via)를 호출해주면 된다.

 

#include<iostream>
using namespace std;

/* n번 원판을 start 에서 dest로 이동 */
void move(int n, int start, int dest){
    cout << start << ' ' << dest << '\n';
}

void hanoi(int N, int start, int dest, int via){
    if (N == 1){
        move(1,start,dest);
    } else {
        hanoi(N-1,start,via,dest);
        move(N,start,dest);
        hanoi(N-1,via,dest,start);
    }
}

 

백준 11729번 기준 막대를 번호로 표현하였기 때문에, 여기서 start,dest,via 모두 int형을 사용했지만

문제와 관련없다면 구현자의 자유이다.