[백준/c++] - 11729 하노이 탑 이동 순서
유명한 수학 문제인 하노이 탑에 대한 알고리즘 문제 입니다.
원반을 하나씩 옮길 수 있을 때, 주어진 입력에 대해서 원반의 최소 이동 횟수와 이동 과정을
출력 하는 것이 요구 사항입니다.
사실 하노이탑 알고리즘 같은 것이 따로 존재 하는지 몰라서 여러 방법으로 30분 정도 생각해 봤는데
도저히 떠오르지 않아 풀진 못했습니다. 규칙이 있는 것은 아닌것 같고, DFS를 이용하면 정답을 구하지 못하고
루프에 빠질 것 같아서, BFS를 이용해 보려고 했으나...
이런 식으로 구현 해버리면 문제가 너무 복잡해진다고 판단했습니다.
그렇게 하노이의 탑 알고리즘을 적용하여 문제를 풀면 이와 같은 간단한 코드가 나오고,
실제로 대부분의 정답 코드들과 인터넷에 떠도는 정답들도 이런 형태의 코드로 구현한것을 확인했습니다.
재귀를 이용한다는 것은 알겠으나, 실제로 코드를 보면 이 코드가 왜 정답인지 의문을 품지 않을 수가 없었습니다.
따라서 코드를 나름대로 분석 해봤습니다.
해당 유튜브 영상을 보고 하노이 탑 알고리즘에 대해 이해한 결과 어느 정도 코드를 이해 할 수 있었습니다.
먼저 원반의 개수가 몇개 이던간에 하노이 탑 알고리즘은 다음과 같은 규칙을 가집니다.
1. 첫번째 기둥(원판)의 원반 n-1개를 두번째 기둥으로 옮긴다.
2. 첫번째 기둥의 n번째 원반을 세번째 원반으로 옮긴다.
3. 두번째 기둥의 n-1개의 원반을 세번째 원반으로 옮긴다.
이게 가능한 이유는 2개, 3개, ..., n-2개의 원반을 옮기는 원리를 이용해 n-1개의 원반을 이동 시킬 수 있는 이유에서 였습니다.
즉, 4개의 하노이 탑 문제는 3개의 원반을 세번째 기둥이 아닌 두번째 기둥에 옮기고, 4번째 원반을 세번째 기둥에
옮긴후에 다시 3개의 원반을 세번째 기둥에 옮기는 과정을 따릅니다.
5개의 하노이 탑 문제도 마찬가지로 4개의 하노이탑 문제의 답을 이용하여 구할 수 있습니다.
큰 답을 구하기 위해 작은 문제들을 해결해 나가기 때문에 이 문제는 재귀를 이용합니다.