[백준 / BOJ] - 11729번 하노이 탑 이동 순서 C++ 풀이

---

 

백준 - 단계별로 풀어보기 [11729] 

https://www.acmicpc.net/problem/11729

문제

 

 

하노이의 탑 문제이다. 1번 장대에 순서대로 쌓여있는 N개의 원판을 어떻게 해야 최소한의 이동을 통해 3번 장대로 모두 이동시킬 수 있는지 최소 횟수와 수행 과정을 출력하는 문제이다.

 

풀이

 

정석적인 하노이 탑의 풀이 방법을 따르면 된다.

1번 장대에 있는 원판을 3번 장대로 모두 옮기기 위한 방법은 무조건 동일한 절차를 따른다.

 

먼저 n-1개의 원판을 3번 장대를 거쳐 2번 장대로 옮기고,

1번 장대에 있는 가장 큰 크기의 원판을 3번 장대로 옮긴 후,

2번 장대에 있는 n-1개의 원판을 1번 장대를 거쳐 3번 장대로 올려 놓는 과정이다. 

 

이를 그대로 알고리즘화하면 쉽게 풀 수 있다.

 

또한, 최소 횟수의 경우에는 하노이 탑에서 원판의 개수가 N일때, 

2^N - 1 의 횟수가 최소 횟수이다.

코드

 

#include <iostream>
using namespace std;
void hanoi(int n, int start, int to, int bypass)
{
    if(n == 1)
        printf("%d %d\n", start, to);
    else
    {
        hanoi(n-1,start,bypass,to);
        printf("%d %d\n",start,to);
        hanoi(n-1,bypass,to,start);
    }
}
int main() {
    int num;
    cin >> num;
    cout << (1<<num) -1 << "\n";
    hanoi(num,1,3,2);
}

1 << num 은 2^num 을 표현한 방식이다.

만약 해당 문제에서 pow(2,num)을 사용하였다면, double형을 활용하는 pow의 특성상 입력 최대값인 20이 입력되면 오차범위가 커져 틀렸습니다. 라는 메세지가 출력된다.

따라서 (int)pow(2,num); 을 활용하던가, 아니면 (1<<num) 같이 시프트 연산을 활용한 표현을 사용해야 한다.

 

평가

 

하노이의 탑에서 재귀적인 관계를 바로 찾을 수 있다면 금방 풀 수 있는 문제이다.

또한 함수의 매개변수에 from과 to외에도 어떤 장대를 지나쳐서 가는지에 대한 정보를 담는 bypass를 매개변수에 반드시 포함을 시켜야만 풀 수 있다.