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

백준 11729 (하노이 탑 이동순서)

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

11729번: 하노이 탑 이동 순서

---

하노이 탑은 유명한 문제지만 막상 구현 과정은 꽤 어렵다.

문제에서는 1~N까지 쌓여있는 하노이탑을 특정 rod로 옮기는 것이기 때문에 가장 기본적이 하노이 탑 문제라고 할 수 있다.

 

설명

---

1~N까지 차곡차곡 쌓여있는 탑을 어떻게 다른 탑으로 옮길까?

하노이 탑의 특성상 위에 놓일 탑은 아래에 있는 탑보다 항상 크기가 작아야 하기 때문에 꽤 복잡한 아이디어를 쓴다.

그림을 보며 이해해보자.

1번 rod에 쌓여있는 1~N까지의 하노이탑을 3번 rod로 옮기려고 한다.

• 1. N번 탑 위에 존재하는 1~N-1까지의 탑들을 2번 rod로 옮긴다.
• 2. N번 탑을 3번 rod로 옮긴다.
• 3. 2번 rod에 존재하는 1~N-1까지의 탑들을 3번 rod로 옮긴다.

위의 과정의 경우 1번에서 2번을 거쳐 3번으로 진행되는 것을 볼 수 있다.

 

탑은 한번에 하나밖에 옮길 수 없기 때문에 1~N-1의 탑들을 어떻게 옮길까?

재귀를 이용하면 된다.

위 과정에서 한가지 빠진 조건이 있는데 탑을 옮길 때 내가 현재 있는 rod를 제외한 두 노드에도 그 탑을 놓을 수 있어야 한다. (이는 더 심화된 하노이탑 문제에서 다룰 예정)

그러나 이 문제의 경우 한 rod에 1~N까지의 탑들이 모두 쌓여져 있고 재귀를 통해 결국 1번탑부터 움직이기 때문에 위의 초록색 조건은 생각할 필요가 없다.

 

즉, 위의 과정을 일반화하여 코드로 구현하면 된다.

코드를 살펴보기 전에 하노이탑의 이동횟수를 구해보자.

A(𝑛) = 1~n번까지의 하노이탑을 특정 rod로 옮기기 위한 횟수라고 하면,

A(𝑛) = 위의 1번과정에서 걸리는 횟수 + 2번과정에서 걸리는 횟수 + 3번과정에서 걸리는 횟수 일것이다.

1번과정 : A(𝑛-1)

2번과정 : 1

3번과정 : A(𝑛-1)

 

즉, A(𝑛) = 2*A(𝑛-1) - 1 이다.

이를 일반식으로 풀어내면 A(𝑛) = 2^n - 1 이다.

 

이 문제에서는 중간의 과정을 출력해야 하기 때문에 재귀를 돌지만,

1~N까지 쌓인 하노이 탑을 (남은 두 rod에 모두 놓을 수 있을 때) 특정 rod로 옮길 때의 횟수는 2^n - 1 임을 기억해놓으면 좋다.

 

구현

---

#include <iostream>
using namespace std;

void go(int n, int start, int mid, int end){
    if(n==1){
        cout<<start<<" "<<end<<"\n";
        return;
    }
    go(n-1,start, end, mid);
    cout<<start<<" "<<end<<"\n";
    go(n-1, mid, start, end);
}

int main(){
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int n;
    cin>>n;
    cout<<(1<<n)-1<<"\n";
    go(n, 1,2,3);
    return 0;
}

start에서 mid를 거쳐 end로 가는 구현이다.