백준 11729번 _ Hanoi / recursion 재귀 문제 (C++)

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

11729번: 하노이 탑 이동 순서

어제 새벽에 꽤나 기싸움 끝에 풀어냈던 문제이다.
하노이탑 문제는 재귀 관련된 문제 중에서 매우 유명하고 대표적인 문제이다. 
재귀 문제의 핵심은 답안의 규칙성을 찾아내는 것이다.
물론 문제가 쉽거나 독자분이 매우 똑똑하여 한 눈에 규칙성이 눈에 보일수도 있지만,
대게는 몇 단계 정도까지 직접 그리거나 써보면서 그 규칙성을 찾는 것이 좋다.

한 번 칩이 1-4개일때 정도까지 규칙성을 찾아보자

1개
1 3

2개 (여기서 우리는) 
1 2 (밑에 원판을 빼내기 위해서 제일 위에 원판을 목표 고리가 아닌 쪽으로 빼낸 뒤)
1 3 (밑에 원판을 목표 고리로 옮긴 후)
2 3 (처음에 빼냈던 원판을 목표고리로 옮긴다.)

3개 
1 3
1 2
3 2 (이렇게 함으로써 위에 두개를 두번째 고리로 빼냈다)
1 3 (제일 밑에 원판을 목표고리로 옮긴 후)
2 1
2 3
1 3 (위에 빼냈던 두개의 원판을 목표고리로 옮긴다.)

4개
1 2
1 3
2 3
1 2
3 1
3 2
1 2 (위에 세개의 원판을 두번째 고리로 빼냈다.)
1 3 (제일 밑에 원판을 목표고리로 옮긴다.)
2 3
2 1
3 1
2 3
1 2
1 3
2 3 (위에 빼냈던 원판을 목표고리로 옮긴다.)

규칙성이 보이는가?!

n개의 원판을 목표고리로 옮기기 위해선
1. (n-1)개의 원판을 다른 고리로 옮긴 후
2. 제일 밑에 원판을 목표고리로 옮기고 
3. (n-1)개의 원판을 다시 목표고리로 옮긴다.

그리고 그 (n-1)개의 원판은 다시,
1. (n-2)개의 원판을 다른 고리로 옮긴 후
2. 제일 밑에 원판을 목표고리로 옮기고 
3. (n-2)개의 원판을 다시 목표고리로 옮겨야 한다.

하노이탑은 명백한 재귀의 문제였던 것이다.
이제 이를 바탕으로 알고리즘을 작성해보자.
사실 몇번 옮겨갔는지는 2^(n)-1로 계산이 되는데 이는 2*(n-1)+1번씩 재귀한다는 특성 때문이다.
하지만 직관적으로 알기 위해서 계산하는 함수를 그냥 구현해보았다.

#include <iostream>
using namespace std;

void hanoi(int num, int start, int etc, int end); //hanoi 원판 옮기는 거 출력 함수
int counter(int num); //몇번 옮겼는지 세는 함수

int main(){
	//재귀함수 특성상 시간이 오래걸려서, cin cout을 stdio와 연결을 끊어줌으로써 성능을 향상시켰다.(굳이 안해도 됨)
    std::ios_base::sync_with_stdio(false); 
    int num;
    cin >> num;
    cout << counter(num) << '\n';
    hanoi(num,1,2,3);
    return 0;
}

int counter(int num){
    int stacker = 1;
    for(int i=1;i<num;i++){stacker = 2*stacker+1;} 
    return stacker;
}

void hanoi(int num, int start, int etc,int end){ //시작고리, 남는 고리, 목표고리
    if (num==1)
    {
        cout<<start<<" "<<end<<"\n"; // 1개라면 바로 시작고리에서 목표고리로 옮긴다.
    }
    else
    {
        hanoi(num-1,start,end,etc); // (n-1)개를 시작고리에서 남는 고리로 옮긴다.
        cout<<start<<" "<<end<<"\n"; // 제일 밑에 것을 시작고리에서 목표고리로 옮긴다.
        hanoi(num-1,etc,start,end); // 남는 고리의 (n-1)개를 목표고리로 옮긴다.
    }
}

 

끝!