[백준/BOJ] 11729번 하노이 탑 이동 순서 (C/C++)

백준 온라인 저지(BOJ) 11729번

www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

* 사용언어 : C언어, C++

 

1. 문제

3개의 장대가 있고 첫 번째 장대에 n 개의 원판이 쌓여있음

다음 규칙에 따라 첫 번째 장대의 모든 원판을 세 번째 장대로 옮김

  1) 한 번에 한 개의 원판만 다른 장대로 옮길 수 있음

  2) 큰 원판을 작은 원판 위에 쌓을 수 없음

이 작업을 수행하는데 필요한 최소 이동 횟수(K)와 순서 출력

 

2. 풀이

재귀 함수의 강력함을 배울 수 있는 하노이의 탑 문제입니다.

복잡해보이는데 사실 몇 가지 규칙만 이해하면 간단한 소스로 풀 수 있습니다.

 

재귀 함수는 n번째를 n-1번째로 어떻게 처리해야하는가? 를 파악하여,

규칙을 찾아 문제를 일반화한다고 생각하면서 풀면 됩니다.

 

일반화를 하기 위해서는 n을 작은 갯수로 두고 직접 옮긴다고 생각하면서

규칙을 찾기 위해 노력해야합니다.

(저도 2개, 3개, 4개의 판까지 손으로 그리면서 직접 풀어보았습니다)

 

제가 찾은 일반화된 결론은 다음과 같고, 아래 코드에서 solve 함수 내에 구현했습니다.

 

  n개의 판을 from장대에서 to장대로 옮기려면 아래와 같이 이동한다.

   1) n-1개의 판을 from장대와 to장대가 아닌 남은 remain장대로 옮긴다.

   2) from장대에 남은 n번 판을 to장대로 옮긴다.

 

 

하노이의 탑 문제가 뭔지 유튜브 영상 등을 통해 풀이법을 확인해보시고

재귀 함수를 작성하기 위한 일반화를 직접 해보시면 도움이 될 것 같습니다.

 

3. 코드

#include <stdio.h>
#include <cmath>

// n개의 판을 from 기둥에서 to 기둥으로 옮긴다
void solve(int n, int from, int to) {
	if (n == 0) return; // 남은 판 없으면 종료

	int remain = 6 - from - to; // 기둥(1,2,3) 합이 6이므로

	solve(n - 1, from, remain);
	printf("%d %d\n", from, to);
	solve(n - 1, remain, to);
}

int main() {
	int n;
	scanf("%d", &n);

	int k = pow(2, n) - 1; // 이동 횟수 : n 일때 2^n - 1

	printf("%d\n", k);
	solve(n, 1, 3);
	
	return 0;
}

* k 값은 solve 함수 호출 횟수로 표현하려했으나, 이동 순서를 계속 메모리에 담아두는 것이 비효율적인 것 같아 일반화하여 먼저 출력하였습니다.