- 문제
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
-
한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
-
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
-
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다. (그림 생략)
- 입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.
- 출력
첫째 줄에 옮긴 횟수 K를 출력한다.
두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.
-
예제 입력 1
3
-
예제 출력 1
7
1 3
1 2
3 2
1 3
2 1
2 3
1 3
해결 전략
본 문제는 C언어 기초를 공부할 적에 대부분이 해결해본 경험이 있을, 매우 대표적인 재귀 연습 문제인 하노이 탑 이동 순서 문제이다. 풀이 아이디어는 아래와 같은 서술로 요약할 수 있음을 모두 알 것이다.
from의 맨 아래 원판을 제외한 n-1개를 from에서 to를 거쳐 through으로 옮겨둔다.
이어서 from의 맨 아래 원판을 to로 옮긴다.
마지막으로 through에 있는 n-1개의 원판을 from을 거쳐 to로 옮긴다.
이러한 기초 문제를 본 벨로그에 포스팅하는 이유는 본인이 최초 시도에서 '시간 초과'가 떴기 때문이다. 이유는 바로 cout의 느린 출력속도 때문이다. 본인은 이를 이미 잘 알고 있음에도, 특별히 문제없을 것이라 예단하고 iostream의 cin/cout을 stdio의 printf/scanf와 속도를 동기화시켜주는 문구를 사용하지 않았다. 바로 이 부분에서 시간 초과의 원인이 발생한 것이다.
이를 곧바로 인지하고, 궁금해서 실제 프롬프트 화면에서의 출력 속도를 비교해보았는데, 확연히 눈에 보일 정도로 차이가 났다. 본인은 여태까지 이를 알면서도 간과하고 있었는데, 본 문제의 경험을 통해 이를 확실하게 몸으로 느꼈다. 앞으로는 알고리즘 문제 해결 및 실제 현업 프로그래밍에 있어서 cin/cout의 속도 저하를 유심히 관찰할 것이라 다짐하고자 본 포스팅을 올린다. 아래는 코드이다.
#include <iostream>
// BOJ - 11729 Hanoi Tower Moving Order
using namespace std;
void hanoi(int n, int from, int through, int to) {
if (n >= 1) {
hanoi(n - 1, from, to, through);
cout << from << " " << to << '\n';
hanoi(n - 1, through, from, to);
}
}
int main(void) {
int n, cnt = 1;
ios_base::sync_with_stdio(false); // 매우 중요!! 이 부분 생략 때문에 최초 시도 실패
cin.tie(NULL); cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) cnt *= 2;
cnt--; cout << cnt << '\n';
hanoi(n, 1, 2, 3);
return 0;
}