BOJ 11729번 하노이 탑 이동 순서

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

 

문제에서 하노이탑을 이동한 과정을 보면 

원판이 3개 일때

1 3

1 2

3 2

1 3

2 1

2 3

1 3

의 순서대로 옮긴 것을 확인할 수 있다. 정답을 기준으로 따라가보면

이는 원판이 3개라고 가정했을 때 최종적으로 장대1의 원판3개를 장대3으로 옮기기 위한 과정은

 

1을 장대3 => 2을 장대2 => 1을 장대2 로 옮겨서 장대1:3 // 장대2:12 // 장대3:x 로 옮겼다는 것을 볼 수 있다.

이는 장대1의 원판의 남은 갯수가 1이 되도록 다른 원판을 장대2로 옮긴 것이다. (알고리즘1)

그리고 나서 장대1의 3을 장대3으로 옮겼다. (알고리즘2)

그리고 나서 장대2의 1,2를 장대3으로 옮겼다. (알고리즘3)

 

이 3가지의 분할 알고리즘으로 하노이 원판을 이동시킬 수 있다.

 

#include <cstdio>
 
int cnt = 1;
 
// in -> 남은 원판개수
// f -> 보내는 장대
// s -> 받는 장대
// none -> 쓰이지않는 장대
void hanoi(int in, int f, int s, int none) {
 
    if (in == 1) {
        printf("%d %d\n", f, s);
    }
 
    else {
        hanoi(in - 1, f, none, s);
        hanoi(1, f, s, none);
        hanoi(in - 1, none, s, f);
    }
 
}
 
int main() {
    int N;
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++)
        cnt *= 2;
 
    printf("%d\n", cnt - 1);
    hanoi(N, 1, 3, 2);
}