[ BOJ 백준 11729번 - 하노이 탑 이동 순서 ] 해설 및 코드

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

11729번: 하노이 탑 이동 순서

 

 

목적

세 개의 장대를 이용하여 첫 번째 장대에서 세 번째로 모든 원판을 옮겨야 한다.

 

접근법

1. 재귀식을 세워보자.

- move(i, j, n)는 i장대에서 j장대로 n개의 원판을 이동시킨다.

- 이러한 move(i, j, n)는 다음과 같이 나타낼 수 있다. 

- move(i, j, n) = move(i, k, n-1) + move(i, j, 1) + move(k, j, n-1)

- 위 식을 설명하자면, 만약, a장대에서 b장대로 5개의 원판을 옮기려면, c장대를 이용해서 먼저 a장대에서 c장대로 4 개를 옮긴 후, a 장대에 남은 1개를 b 장대로 옮긴다. 마지막으로 c 장대에서 n-1개를 b 장대로 옮긴다.

 

2. 결과의 출력은 일일히 하기보단, char형 배열에 저장하여 마지막에 출력해준다.

 

#include<cstdio>
 
char ans[1 << 22];
int i=0;
void move(int from, int to, int n) {
    if (n == 0)return;
    int via = 6 - from - to;
    move(from, via, n - 1);
    ans[i++] = from + '0';
    ans[i++] = ' ';
    ans[i++] = to + '0';
    ans[i++] = '\n';
    move(via, to, n - 1);
}
 
int main() {
    int n; scanf("%d",&n);
    printf("%d\n",(1<<n) - 1);
    move(1, 3, n);
    puts(ans);
}