[C언어] Backjoon_Code 11729, 하노이 탑 이동 순서

| 문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

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

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

 

| 입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

 

| 출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

 

| 예제 입력 1

3

| 예제 출력 1

7
1 3
1 2
3 2
1 3
2 1
2 3
1 3

 

| 문제의 키 포인트

1. 하노이의 탑의 이동 규칙을 파악하자.

> 제약 조건 1: 원반은 한 번에 하나씩만 옮길 수 있다.

> 제약 조건 2: 옮기는 과정에서 작은 원반의 위에 큰 원반이 올려져서는 안된다.

2. 작은 예시를 통해 이해하자.

(1) 작은 원반 n-1 개를 'A'에서 'B'로 이동

(2) 큰 원반 1개를 'A'에서 'C'로 이동

(3) 작은 원반 n-1 개를 'B'에서 'C'로 이동

3. 이를 통해, 원반 n개를 이동하는 문제는 원반 n-1개를 이동하는 문제로 쪼개진다는 것을 알 수 있고, 이는 재귀함수를 이용하면 되겠습니다.

 

| 해결방안(Solution)

사실대로 말씀드리면, 어떻게 구현해야 하나... 잘 모르겠어서 구글링을 해봤습니다.

하노이의 탑 문제는 코딩을 하는데 있어 한번쯤은 꼭 거쳐가는 문제라고 하더군요.

그래서인지, 위키피디아에서 다양한 소스코드를 찾아볼 수 있었습니다.

C언어에 대한 코드는 없었지만, C++ 코드를 보고 유추하여 작성해보았습니다.

 

| 소스코드(SourceCode)

// BOJ_11729_Tower_of_Hanoi, 하노이의 탑
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>

void move(int from, int to);
void hanoi(int n, int from, int by, int to);

int main(void)
{
	int N, cnt;
	scanf("%d", &N);

	cnt = (int)pow(2, N) - 1; // 메르센의 수
	printf("%d\n", cnt);

	hanoi(N, 1, 2, 3);
}

void move(int from, int to)
{
	printf("%d %d\n", from, to);
}

void hanoi(int n, int from, int by, int to)
{
	if (n == 0)
	{
		return;
	}
	else
	{
		hanoi(n - 1, from, to, by);
		move(from, to);
		hanoi(n - 1, by, from, to);
	}
}

출력에서 가장 먼저 출력되는 총 이동 횟수의 경우, 하노이의 탑 내용에서 2ⁿ-1번 이동으로 모든 원판을 이동시킬 수 있다는 내용을 토대로 계산하였습니다.

 

| 문제출처

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

11729번: 하노이 탑 이동 순서