BaekJoon 11729번: 하노이 탑 이동 순서

풀이법

1) N의 크기가 크지 않기에 재귀함수로 풀 수 있는 대표적인 문제이다.

2) 귀납적인 사고를 통해 문제를 해결하는 것이 Key point이다.

    1->3, 1->2, 2->3 등과 같이 기존에 절차 지향적으로 문제를 해결했던 분들에게는 어려웠을 문제라 생각된다.

    어렵겠지만, 'k-1번째에서 가능하면 k 번째에서 가능하다'와 같은 귀납적인 사고를 이용한다면 문제를 수월하게 해결      할 수 있을 것이다.

3) 위의 그림에서 장대를 각각 stack 이라 부르고, 원판을 pan이라고 임의로 칭하겠다.

    3번 stack에 5번 pan을 올리기 위해서는 2번 stack에 n-1번 pan까지 올려야한다. (핵심)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <math.h>
#define INF 1000000001
using namespace std;
int n;
void hanoi(int from, int to, int count)
{
	if (count == 1)
	{
		cout << from << " " << to << "\n";
		return;
	}
	hanoi(from, 6 - from - to, count - 1);
	hanoi(from, to, 1);
	hanoi(6 - from - to, to, count - 1);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	cout << (int)pow(2, n) - 1 << "\n";
	hanoi(1,3,n);
}

한계점 및 개선사항 (+주의사항)

재귀에서 가장 중요한 것은 base condition으로 언제 재귀를 종료할 지 명시하는 것이다. 이 경우 count가 1일 때를 base condition으로 잡았다. n-1번 pan을 6-from-to stack으로 옮긴 후, n번 판을 to stack으로, 다시 n-1번 pan을 to stack으로 옮기는 과정을 재귀 함수 3개로 표현하였다. 총 옮기는 갯수는 간단한 등비 수열인 2^n -1이 나옴을 문제를 풀다보면 알 수 있다. C++이용자에게 주의점은 pow()함수는 실수 값을 return 하기에, (int)를 사용해서 강제 형 변환을 하지 않으면 채점 시 틀릴 수 있다.

 

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest