백준 문제풀이 : (11729) 하노이 탑 이동 순서 - C/C++

문제 : https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

시간 제한	메모리 제한	난이도	알고리즘 분류
1초	256 MB	Gold 5	재귀

 

 

문제

 

 

풀이

재귀함수의 대표격 사례인 하노이의 탑이다. 사실 나는 재귀함수를 아직도 많이 어려워하는 편이다. 쉬운 문제들은 간단히 풀리기도 하지만, 문제가 복잡해질 수록 종료조건과 재귀호출 매개변수를 어떻게 구성해야할 지 감도 안잡힐때가 많았다.

 

원판의 변화를 손으로 그려가보며 재귀의 구조를 설계해보려고 했지만 뇌의 한계인지 좀처럼 해결되지 않았다. 구글링을 통해 간단하게 스터디를 진행한 후 다시 문제를 풀어보았다. 스터디를 통해 대략 알게된 점은, 재귀 문제는 함수 내의 구조를 세세하게 이해하기보다는 규칙을 발견하고 그 규칙을 그대로 코드로 옮겨놓는 게 더 중요하다는 사실이었다. 

 

무슨 뜻이냐면, 우선 코드를 먼저 들여다보면 원반을 옮기는 재귀 함수는 아래와 같이 구성할 수 있다.

void hanoi(int n, int s, int e, int m) {
    if (n==0) return ;
    
    hanoi(n-1, s, m, e);
    printf("%d %d\n", s, e);
    hanoi(n-1, m, e, s);
}

 

n은 옮겨야하는 원반의 개수, s는 옮길 원반의 시작 기둥, e는 종료 기둥, m은 중간 기둥이다. 나는 위 처럼 hanoi() 함수를 작성했지만 위 구조가 반복될 때 마다 값 변수들이 어떻게 변경되며 왜 위의 구성이 정답인지에 대해서는 명확하게 설명하지 못한다. 재귀에 더 익숙해진다면 언젠가 가능할지도 모르겠으나 아직은 어렴풋하다.

 

내가 한 일이라고는 단지 원반을 옮기는 과정에서 규칙을 찾아내, 그를 식으로 만든 후 그대로 코드화 시켰을 뿐이다. N개의 원반을 s기둥에서 e 기둥으로 옮기는 규칙이란 다음과 같다. s기둥에 N개의 원반이 걸려있으며, 맨 아래에서부터 n번째, n-1번째, n-2번째... 1번째 기둥이라고 치자. 

 

1. n-1개의 원반을 s기둥에서 m기둥으로 옮긴다. (s → m)

2. n번째 원반을 s기둥에서 e기둥으로 옮긴다. (s → e)

3. n-1개의 원반을 m기둥에서 e기둥으로 옮긴다. (m → e)

 

원반의 개수가 몇 개이든 상관없다. 모든 경우의 수에서 우리는 1번째부터 n-1번째까지 n-1개의 원반을 먼저 s기둥에서 m기둥으로 옮긴 후, 가장 면적이 넓은 n번째 원반을 s기둥에서  e기둥으로 옮기고, 그리고 다시 m기둥에 쌓았놨던 n-1개의 원반을 e 기둥으로 옮기는 작업을 반복하게 된다. 이것이 하노이의 탑 규칙이다.

 

식으로 요약하면 아래와 같을 것이다.

f(n) = n개의 원반을 s기둥에서 e기둥으로 옮기는 행위

f(0) =  함수 종료

f(n) = f(n-1) + 1 +f(n-1)  // 1 은 가장 넓은 원반을 s에서 e로 옮기는 행위

 

이를 그대로 코드로 옮기면 다음과 같다.

 

 

코드 작성

#include <iostream>
#include <cstring>

using namespace std;

//s : 옮길 원반의 시작 기둥
//m : 운반에 사용되는 거쳐가는 기둥
//e : 옮길 원반의 도착지 기둥
void hanoi(int n, int s, int e, int m) {
    if (n==0) return ;
    
    hanoi(n-1, s, m, e); // n-1개의 원반을 e를 거쳐 s → m 로 옮긴다. 
    printf("%d %d\n", s, e); // n번째 원반을 s → e로 옮긴다.
    hanoi(n-1, m, e, s); // n-1개의 원반을 s를 거쳐 m → e로 옮긴다.
}

int main() {
    int n;
    scanf("%d", &n);
    
    int sum=0;
    for (int i=0, two=1 ; i<n ; i++) {
        sum+=two;
        two*=2;
    }
    
    printf("%d\n", sum);
    hanoi(n, 1, 3, 2); // 1번 기둥이 s, 2번 기둥이 m, 3번 기둥이 e로 작업을 시작한다.
}

 

 

(+) 부가 설명

N이 3일 경우에는 재귀 레벨(깊이)가 1, 2, 3 까지 내려간다.

각 레벨에서 가장 넓은 원반은 1번째, 2번째, 3번째 원반이며, 모든 작업은 결국 각 깊이에서 가장 넓은 원반 1개를 옮기는 작업의 반복으로 이루어져있다고 볼 수 있다. 때문에 위 코드의 printf 문은 모든 원반의 이동을 출력할 수 있다. 

 

깊이 1에서는 원반 1개 옮기는 작업이 1번, 

깊이 2에서는 원반 1개 옮기는 작업이 2번, 

깊이 3에서는 원반 1개 옮기는 작업이 4번 수행된다.

위 코드에서 printf 문을 아래와 같이 변경해 출력하면 각 원반의 이동이 어떤 재귀 레벨(깊이)에서 실행되고 있는지 관찰할 수 있다. 

printf("%d %d, 재귀 레벨(깊이) : %d\n", s, e, 4-n);

//결과
// 1 3, 재귀 레벨(깊이) : 3
// 1 2, 재귀 레벨(깊이) : 2
// 3 2, 재귀 레벨(깊이) : 3
// 1 3, 재귀 레벨(깊이) : 1
// 2 1, 재귀 레벨(깊이) : 3
// 2 3, 재귀 레벨(깊이) : 2
// 1 3, 재귀 레벨(깊이) : 3

 

 

 

END.