백준 11729 - 하노이 탑 이동 순서

 

11729번: 하노이 탑 이동 순서

 

서론

재귀 함수의 기초적인 예제들을 다룰 때 하노이 탑 문제는 자주 등장합니다.

본문에서는 이 하노이탑 문제를 통해 재귀 함수를 이해해보도록 합시다.

 

문제 파악

하노이 탑이 어떻게 동작하는지에 대한 이해만 있다면 문제 자체는 어렵지 않을 수도 있습니다.

다만, 하노이 탑을 해결하는 문제가 어렵기 때문에 다소 복잡한 부분이 있습니다.

 

• 첫 번째 탑에 있는 원반 개수 N을 입력받는다.
• 세 번째 탑으로 원반을 옮기는 최소 횟수를 출력한다.
• 세 번째 탑으로 원반을 옮기는 과정을 출력한다.

 

문제 파악 2 - 하노이 탑 규칙

위의 문제를 보듯이 하노이 탑의 규칙을 수학적으로 풀이를 할 수 있으면 어려운 문제는 아닐 수 있습니다. 

하노이 탑은 다음과 같은 전제조건이 있습니다.

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

이 부분을 수학적 풀이를 하기 전에, 눈으로 원판이 각각 1개 2개 3개일 경우를 살펴보도록 합시다.

 

Case 1 - 원판 1개

원판 한 개일 때 경우를 눈으로 살펴보도록 합시다.

 

 

 

 

• 1번 2번 3번 탑이 있다.
• 원판은 1번 탑에 한 개 존재한다.
• 3번 탑으로 옮겨야 된다.

 

 

 

 

 

 

 

• 하나의 원판은 바로 3 번탑(목표)으로 이동이 가능하다.

 

 

 

 

 

원판이 1개인 경우라면, 보조 탑(2번)을 사용하지 않고, 바로 목표 탑(3번)으로 이동할 수 있다는 것을 알 수 있습니다.

정리하자면, 

시작 기둥의 원판이 1개라면 목표 탑으로 옮길 수 있다.

 

Case 2 - 원판 2개

이제 이어서 원판이 2개인 경우를 살펴보도록 합시다.

 

 

 

• 2개의 원판이 1번 탑에 있다.
• 1번 탑(시작)에서 3번 탑(목표)으로 원판을 모두 옮겨라

 

 

 

 

 

 

 

• 하노이 타워의 규칙에 따라, 가장 큰 원판을 먼저 3번 탑으로 옮겨야 합니다. 
• 그리고 case1에서 본 것처럼 1번 탑에(시작) 하나의 원판만 있어야 3번 탑(목표)으로 이동이 가능합니다.
• 따라서 1 번탑에는 가장 큰 원판 하나만 가질 수 있게 원판을 옮겨 줍니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Case 2를 통해 시작하는 탑에는 가장 큰 원판 1개만이 남아야 목표 탑에 옮길 수 있다는 것을 알았습니다.

따라서 가장 큰 원판은 2번 또는 3번 탑에 쌓을 옮겨야 됩니다. 다만, 하노이 타워의 규칙 원판은 자신보다 작은 원판 위에 올라올 수 없다는 규칙이 있습니다. 이 내용을 정리하자면,

시작 탑에는 옮겨야 하는 가장 큰 원판을 남긴다.

단 가장 큰 원판은 목표 탑에 가장 아래에 가야 되기 때문에

작은 원판은 2번(보조) 탑에 옮겨야 된다.

 

Case3 - 원판 3개

위의 case 1,2의 규칙을 이해하면서 원판이 3개인 경우를 살펴보도록 하겠습니다.

 

 

 

• 해당 case를 보기 전에 case1 , 2를 잘 생각해 보면서 따라오세요
• 우선 가장 큰 원판을 목표 탑으로 옮겨야 됩니다.
• 따라서 보라색, 노란색 원판을 2번으로 옮기는 과정이 필요합니다.

 

 

 

 

 

• 1번(시작)의 보라색 노란색 원판을 2번(목표)으로 옮기는 과정
• 2번에 보라색 노란색으로 원판이 쌓여야 합니다. 
• 1번의 보라색 원판을 2번(목표)에 쌓기 위해서는 노란색 원판을 3번(보조)으로 옮기는 과정이 필요합니다.(case 2의 동작과 동일하다.)

 

 

 

 

 

 

 

• 1번(시작)의 보라색 노란색 원판을 2번(목표)으로 옮기는 과정 2
• case 2와 동일한 동작 

 

 

 

 

 

 

 

 

• 가장 처음 목표인 1번의 3개의 원판을 3번으로 옮기기 위한 첫 번째 과정의 완료
• 가장 큰 원판이 시작(1번) 탑에 남고, 나머지 원판은 보조(2번) 탑에 쌓였다.

 

 

 

 

 

 

 

 

• 이제 가장 큰 원판을 목표 탑(3번)에 옮긴다.
• 그다음. 2번을 시작 탑으로 하고 3번을 목표 탑으로 다시 원판을 옮긴다.

 

 

 

 

 

 

 

 

• 이 또한 case 2와 마찬가지이다.
• 2번 탑에 쌓여있는 가장 큰 원판을 제외하고 보조 탑에 원판을 옮긴다.

 

 

 

 

 

 

 

 

 

• 이후 반복해서 차례대로 원판을 쌓아준다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

부분만을 바라보면 case1과 case 2의 과정을 반복하고 있습니다.

다만, 원판의 개수를 줄여가면서 동작을 수행하고 있을 뿐입니다.

 

이 부분들을 구체화하여 소스코드를 만들면 문제풀이가 가능해집니다.

 

 

소스코드 보기

간단하게 위의 내용을 재귀적 표현으로 구현해 봅시다.

결국 재귀적 함수 호출이 이루어지면서 시작 탑의 원판이 가장 큰 한 개가 남으면 목표 기둥으로 옮기면 됩니다.

즉, 원판의 개수 N에서 계속 -1개씩 줄어들어가며 원판이 1개가 되기 위해서 계속 시작 및 목표 탑을 설정하고 옮겨주면 됩니다.

 

#include <stdio.h>

int Count;


void solve_cnt(int cnt, int start, int end, int temp) {

    //종료 조건 원판이 1개가 되면 옮길 수 있다. 
    if (cnt == 1) {
        Count++;
        return;
    }

    //재귀함수 호출 원판을 하나 빼고, 임시 기둥으로 옮김
    solve_cnt(cnt - 1, start, temp, end);

    //임시기둥으로 옮기기 위한 과정이 종료 후 시작점 부터 총착지 까지의 결과 값 출력
    Count++;

    //다시 재귀함수 호출 중간지점에 옮겨진 원판을 종착지 까지 이동하기 위한 호출
    solve_cnt(cnt - 1, temp, end, start);

    return;
}


void solve_pass(int cnt, int start, int end, int temp) {

    //종료 조건 원판이 1개라면 시작점 부터 종착지 까지의 결과 값 출력
    if (cnt == 1) {
        printf("%d %d\n", start, end);
        return;
    }

    //재귀함수 호출 원판을 하나 빼고, 임시 기둥으로 옮김
    solve_pass(cnt - 1, start, temp, end);

    //임시기둥으로 옮기기 위한 과정이 종료 후 시작점 부터 총착지 까지의 결과 값 출력
    printf("%d %d\n", start, end);

    //다시 재귀함수 호출 중간지점에 옮겨진 원판을 종착지 까지 이동하기 위한 호출
    solve_pass(cnt - 1, temp, end, start);

    return;
}


int main() {
    //원판 갯수

    int N;

    scanf_s("%d", &N);
    solve_cnt(N, 1, 3, 2);
    printf("%d\n",Count);
    solve_pass(N, 1, 3, 2);

    return 0;
}

소스코드 풀이

소스코드를 보면 옮기는 Count++ 또는 printf부분이 원판이 옮겨지는 과정입니다.

재귀적 순서가 동작하는 과정을 살펴보면 아래와 같습니다.

재귀 순서 (깊이)	호출 중인 함수	cnt	start	end	temp
1	solve(3,1,3,2)	3	1	3	2	3개의 원판을 1번에서 3번으로 옮겨라
2	solve(2,1,2,3)	2	1	2	3	2개의 원판을 1번에서 2번으로 옮겨라
3	solve(1,1,3,2)	1	1	3	2	1개의 원판을 1번에서 3번으로 옮겨라 종료조건 만족(옮김) (출력 값 : 1 -> 3)
2	solve(2,1,2,3)	2	1	2	3	2개의 원판을 1번에서 2번으로 옮겨라2 첫번 째 재귀 종료 후 출력(옮김) ( 출력 값 1 -> 2) 두번 째 재귀 호출
3	solve(1,3,2,1)	1	3	2	1	1개의 원판을 3번에서 2번으로 옮겨라 종료조건 만족(옮김) (출력 값 : 3 -> 2)
1	solve(3,1,3,2)	3	1	3	2	3개의 원판을 1번에서 3번으로 옮겨라2 첫번 째 재귀 종료 후 출력 ( 출력 값 : 1 -> 3) 두번 째 재귀 호출
2	solve(2,2,3,1)	2	2	3	1	2개의 원판을 2번에서 3번으로 옮겨라
3	solve(1,2,1,3)	1	2	1	3	1개의 원판을 2번에서 1번으로 옮겨라 종료조건 만족 (출력 값  : 2 -> 1)
2	solve(2,2,3,1)	2	2	3	1	2개의 원판을 2번에서 3번으로 옮겨라2 첫번 째 재귀 종료 후 출력 ( 출력 값 2 -> 3) 두번 째 재귀 호출
3	solve(1,1,3,2)					1개의 원판을 1번에서 3번으로 옮겨라 종료조건 만족 ( 출력 값 : 1 -> 3)

소스코드 동작을 살펴보면 재귀 호출의 깊이 따라 시작 탑과 목표 탑이 변경되면서 case 3과 같이 동일하게 동작합니다.