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

바킹독님 강의를 천천히 들으면서 공부중인데 이제 재귀파트에 왔다. 전에 포스팅했던 (https://pl-are.tistory.com/34) 문제는 재귀 연습문제 1번이었고, 이 문제는 그냥저냥 풀만했다.

하 근데... 이 문제가 진짜 어렵다. 이 문제를 풀면서 내가 재귀를 아직 이해하지 못했고, 절차지향적으로 사고하고 있었다는걸 깨달았다. n이 3일때, 4일때, 5일때 각각 해보면서 순서대로 따라가는건 할 수 있는데, n이 6일때, 7일때... 100일때는? 귀납적으로 사고하지 않으면 풀수가 없다. 고려해야할 사항이 너무 많아서...

 

열심히 쳐다보고 적어보면서 나름대로 이해하려고 노력한 과정을 적어보려고 한다.

 

우선 하노이 탑 문제에 대해 간략하게 설명을 하자면 3개의 탑이 있고, 이 중 1번째 탑에 원판들이 있는데 이 원판들을 3번째 탑으로 이동시키는 방법을 구하는 문제이다. 단, 이동횟수는 최소가 되어야 하고 탑에 원판을 놓을 때 내가 놓을 원판이 이미 놓여져있는 원판보다 클 수 없다. 는 조건이 붙어있는 문제이다.

 

문제를 처음 봤을 때는 당연하게도 절차지향적으로 사고했다. 1번 탑에 있는 작은 원판을 2번 원판..그리고 그 다음 1번 탑 원판을 3번 원판...그리고 다시 2번 탑에 있는 원판을 3번 원판... 이렇게 말이다. 근데 이렇게 풀다가는 n이 커졌을 때의 답은 구할 수가 없게 되고, 다른 방법이 필요하다고 생각해서 강의를 계속 봤다.

 

https://youtu.be/8vDDJm5EewM?t=1219 

이 부분에서 n번 원판을 옮기려면 n-1개의 원판을 옮겨야한다는 부분을 이해하기 위해서 계속 봤다. 

당연한거지만 n번 원판을 1번에서 3번으로 옮기려면 n-1개의 원판을 2번에 두어야 한다. 그래야 n번 원판을 3번에 옮길 수 있기 때문이다. 

그 다음에는 2번에 둔 n-1개의 원판을 3번으로 옮기면 되는데, 이게 끝이다. 진짜 이해가 안 된다 싶었지만 일단 봤다.

n-1개의 원판을 기둥 a에서 6-a-b로 옮기고, n번 원판을 a에서 b로 옮기고, n-1개의 원판을 6-a-b에서 b로 옮긴다.

만약 절차지향적 사고라면 몇번 원판을 어디로 옮기고 몇번 원판을 어디로 옮기고..이걸 다 시뮬레이션 해보겠지만

1일때 된다는걸 확인했으니  앞에 나왔던 도미노처럼 k일때 된다고 가정하고, 그럼 k+1일때도 된다고 가정하기로 했다.

근데 코드는 어떻게 짜야할지 모르겠어서... 코드를 봤다.

간단하지만 어려웠다..ㅠㅠ;

base condition을 위에 두고, 재귀 식 1,2,3번을 그대로 옮겨놓은건데 이해가 참 안되더라.

그냥 받아들이기로 했다. 중간 과정을 시뮬레이션하려고 하지 말고, k일때 되면 k+1일때도 당연히 될거라고 생각하기로..

재귀를 많이 풀면서 익숙해져야 할 것 같다..^^

#include <iostream>
using namespace std;
void hanoi(int a, int b, int n)
{
    if (n == 1)
    {
        cout << a << ' ' << b << ' ' << "\n";
        return;
    }
    hanoi(a, 6 - a - b, n - 1);
    cout << a << ' ' << b << ' ' << "\n";
    hanoi(6 - a - b, b, n - 1);
}
int main()
{
    int n;
    cin.tie(0); ios::sync_with_stdio(0);
    cin >> n;
    cout << (1 << n) - 1 << "\n";
    hanoi(1, 3, n);
}