Baekjoon 11729 하노이 탑 이동 순서

[문제]

[풀이]

해당 문제는 하노이탑 문제로, 아주 유명한 재귀함수 문제이다.
작년, 자료구조 시간에 Stack으로 풀 수 있는 문제의 예시로 공부한 적 있는데,
재밌는 점은 LIFO의 특징을 가지는 Stack으로는 풀 수 있지만 FIFO의 특징을 가지는 Queue로는 풀 수 없다는 점 ! 이건 그림을 보면 바로 이해가 되는데, 당연하게도 제일 위에 있는 원부터 꺼내야하기 때문이다.

하노이 코드는 해당 코드를 암기하는 것이 가장 편한 방법이다.

void hanoi(int n, int fro, int by, int to))
{
    if (n == 1)
    {
            printf("%d %d\n", fro, to);
            return;
    }
    else
    {
        hanoi(n - 1, fro, to, by);
        {
            printf("%d %d\n", fro, to);
        }
        hanoi(n - 1, by, fro, to);
        return;
    }
}

내가 이 코드를 이해하는 방식은 다음과 같다.
1. 출발점에서 시작해서 도착지를 거쳐 보조축으로 !
2. 보조축에서 시작해서 출발점을 거쳐 도착지로 !

나는 이 두 문장만 기억하면 함수의 매개변수의 위치가 달라지더라도
헷갈리지 않고 쉽게 코드를 만들어낼 수 있더라 !

나는 이 코드를 작성할 때, cstdio를 사용했는데 그 이유는 cin/cout보다 scanf/printf가 더 빠르기 때문 ! 이전에 비슷한 하노이탑 문제를 시도했는데 시간초과가 떠서 수정했고, 이 문제의 코드도 똑같이 반영해서 cstudio를 사용해 scanf/printf로 코드를 짜보았다.

[최종코드]

#include <cstdio>
void hanoi(int n, int fro, int by, int to))
{
    if (n == 1)
    {
            printf("%d %d\n", fro, to);
            return;
    }
    else
    {
        hanoi(n - 1, fro, to, by);
        {
            printf("%d %d\n", fro, to);
        }
        hanoi(n - 1, by, fro, to);
        return;
    }
}

int main(void)
{
    int n;
    int num=1;
    int idx = 1;
    scanf("%d", &n);


    printf("%d\n",(1<<n)-1);
    hanoi(n, 1, 2, 3);
    return 0;
}

[돌아보며]

이 문제 푼지 오래됐는데 풀자마자 안하니까 그때랑은 또 느낌이 다른네.
담부턴 문제 풀자마자 바로 코드 리뷰, 벨로그 작성해야겠다.

요즘엔 시간초과랑 답이 나오는데도 틀렸습니다가 떠서 쉬운 문제를 꾸준히 풀고있는데...
이제 시간 여유나니까 여러 자료 보고 공부하면서 다시 도전해봐야겟당 휴 ㅠㅠ