백준 하노이의 탑 분석 설명

자료구조를 배우다보면 배우는 하노이의 탑 여전히 그때나 지금이나 직접 생각해서 짜려면 생각보다 곤란하다.

하노이의 탑은 재귀를 사용했지만 재귀를 사용할줄 아는 사람이 직접 구현하는 것보다 이미 구현되어있는 구현 순서를 쉽게 생각해내는 것이 더 빠르고 정확하다.

내가 원숭이라는 증명인걸까?

하노이의 탑은 A, B, C 의 봉 3개에서 A에서 C로 모든 원반을 옮기는 것을 목표로 한다.

각 규칙은 아래와 같다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이미 이 글까지 보러왔다면 다 알고 있는 내용이라고 생각한다.(문제에 적혀있으니까..)

하노이의 탑을 어떻게 구현하느냐 아니다. 어떻게 진행되는지 생각해보자.

원반이 총 3개인 경우로 생각하고 기억하는 것이 마음에 편하고 정신건강에 좋다.

그럼 일단 1,2 원반을 B봉에 다 옮겨야한다. 그리고 나머지 3 원반은 C에만 가면 된다.

그러니까 A에서 C를 거쳐 B까지 N-1개 가 옮겨지면 된다는 것이다.

이걸 함수로 적어보자.

void Hanoi(int num, int A, int B, int C){
    Hanoi(num-1, A, C, B);
}

N-1개가 A에서 C를 거쳐 B로 간다.

그럼 그 다음에 B에 있는 원반 1 2를 어떻게 옮기느냐? A를 거쳐 C로 간다.

N-1개가 B에서 A를 거쳐 C로간다.

Hanoi(num -1, B, A, C);

그럼 n이 1인 경우에는 어떻게 될까?

사실 처음 원반 1 2를 B로 옮기고 나머지 3은 그냥 C로 옮기면된다. n이 1인경우에 C로 바로 옮기면된다.

if(num == 1){
        cout << A << ' ' << C;
    }

A B C라고 생각하면 생각하면 문제에 접근하기 좋지만 이는 기억에 잘 남지가 않는다.

여기서 영어가 등장한다. A를 FROM으로 b를 bY로 c를 tO로 한다.

void Hanoi(int num, int from, int by, int to){
    if(num == 1){
        cout << from << ' ' << to << '\n';
    } else {
        Hanoi(num-1, from, to, by);
        cout << from << ' ' << to << '\n';
        Hanoi(num-1, by, from, to);
    }
}

그리고 3개의 원반의 경우 저 함수가 딱 맞아 떨어진다.

궁금하면 직접 실행해보고 저렇게 생각해서 짜는게 정말 편하다.