백준 문제 링크 : 1914번: 하노이 탑 (acmicpc.net)
백준 1914번 하노이 탑 문제 사진
문제 요약
입력 값 : N( 1 <= N <= 100)
- 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
- 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
문제 풀이 과정
오늘은 어제 갑자기 생각난 하노이 탑 문제를 풀어보려고 합니다. 예전에 프로그래밍을 배우고 얼마 되지 않았을 때 이 문제를 접하게 되었는데 그때는 아무리 생각해도 모르겠어서 넘어갔었는데 지금은 풀 수 있을 것 같아서 이렇게 풀어봤습니다.
하노이 탑 문제를 요약하면 크키가 큰 원판이 크기가 작은 원판 위에 올라가지 않도록 하면서 탑을 1번에서 3번 자리로 옮기는 문제입니다. 굉장히 유명한 문제이고 또 현실에서도 완구로 판매되고 있는 문제이기도 하죠.
이 문제를 해결하면서 이동 과정을 n의 값이 20 이하일 때만 출력하고 20 이상이면 이동 횟수만 출력하여야 합니다.
하노이 탑 직접 풀어보기
알고리즘을 확립하기 위해 직접 문제를 해결해보도록 합시다. 가장 쉬운 경우부터 살펴보기 위해 2층으로 먼저 풀어봅시다.
위 영상을 보면 상단 층이 목표 공간과 현재 공간을 제외한 나머지 공간으로 이동 후 하단 층이 목표 공간으로 이동하고 기존에 있던 층을 목표 공간으로 이동 시키면서 탑이 이동 되는 것을 볼 수 있습니다.
이를 순서대로 나열해보면
- 가장 밑 층을 제외한 나머지를 옮기고자 하는 공간과 현재 탑이 있는 공간을 제외한 나머지 공간에 이동시킨다.
- 가장 밑 층을 옮기고자 하는 자리에 옮긴다.
- 나머지 층들을 옮기고자 하였던 부분으로 이동시킨다.
하노이 탑 문제에 층 수가 추가된다고 하더라도 위의 과정이 반복되면서 진행되게 되죠. 이를 확인하기 위해 아래 3층 또한 풀이해보았습니다.
만약 3개의 원판이 쌓여있는 상태에서 탑을 3번 자리로 옮기기 위해서는 아래와 같은 과정을 거쳐야 해요.
위 과정을 목록으로 정리해보면
- 3층 타워를 1->3으로 옮기고자 한다
- 위 2개 층을 1(현재 장소) -> 2(목표 장소)으로 이동
- 1번 층을 1(현재 장소) ->3(나머지 장소)으로 이동
- 2번 층을 1(현재 장소) ->2(목표 장소)으로 이동
- 1번 층을 1(나머지 장소) -> 2(목표 장소)으로 이동
- 3번 층을 1(현재 장소) -> 3(목표 장소)로 이동
- 옮겨둔 2개 층을 2(현재 장소) -> 3(목표 장소)으로 이동
- 1번 층을 1(현재 장소) ->3(나머지 장소)으로 이동
- 2번 층을 1(현재 장소) ->2(목표 장소)으로 이동
- 1번 층을 1(나머지 장소) -> 2(목표 장소)으로 이동
이렇게 정리할 수 있습니다. 각 과정이 재귀적으로 3단계를 거쳐 진행됨을 알 수 있습니다. 때문에 이를 재귀 함수를 이용하여 풀면 아주 손쉽게 푸는 것이 가능합니다.
그럼 이제 재귀 함수에서 목표 공간과 현재 공간이 아닌 나머지 공간을 찾아내는 방법에 대해 알아보도록 합시다.
공간은 총 3개로 1에서 3으로 이동하기 위해선 2번 공간을 거쳐가야 합니다. 다른 경우들도 살펴보면 (2 ->3 = 1)(3 -> 1 = 2)(2->1 = 3) 등이 있죠 이곳에서도 규칙을 찾아볼 수 있습니다. 현재 공간 갯수인 3에 (from+to)를 3으로 나눈 나머지를 빼주면 나머지 공간이 나오게 되죠.
식을 만들면 (3 – (from + to) % 3)이 되며 이를 이용해 나머지 장소의 위치를 구할 수 있습니다. 이렇게 구한 위치로 탑을 옮기고 마지막 장소로 다시 옮겨가며 문제를 풀면 됩니다.
횟수의 크기 문제 해결
일단 이렇게 하노이 탑을 푸는 방법은 이제 알았습니다. 다만 이동 횟수를 출력하는 부분에서 또 다른 문제가 발생합니다. n은 최대 100으로 입력될 수 있는데 이 경우 하노이 탑 알고리즘을 그대로 이용하면서 이동 횟수를 계산이 너무 오래 걸리죠. 하지만 직접 하노이 탑 문제를 풀어보면서 이동 횟수를 구해보면 어떤 규칙을 찾아볼 수 있습니다.
[n = 1, result = 1] [n = 2, result = 3] [n = 3, result = 7]…
21 – 1 , 22 – 1, 23 – 1 …..
(0 * 2 + 1), ((0 * 2 + 1) * 2 + 1), ((0 * 2 + 1) * 2 + 1) * 2 + 1 …..
위와 같은 방식으로 횟수가 늘어나는 것을 확인할 수 있습니다. 이를 계산하여 먼저 연산 횟수를 출력하고 n의 크기가 20 이하인 요소들만 이동 과정을 출력하도록 만들어 주면 됩니다.
이때 주의해야 할 점은 숫자 크기가 정수형의 최대 크기를 벗어나기 때문에 배열로 자리 당 값을 저장하여 출력하는 것이 좋습니다.
코드는 아래와 같습니다.
#include <iostream>
#include <vector>
using namespace std;
//이동 처리
void move_a2b(short a,short b){
cout << a << " " << b << "\n";
}
//하노이 타워 이동 처리
void hanoi_tower(short from,short to,short count){
if(count == 0) return;
hanoi_tower(from, 3 - (from + to ) % 3,count-1);
move_a2b(from,to);
hanoi_tower(3 - (from + to ) % 3,to,count - 1);
}
int main()
{
ios::sync_with_stdio(false);
int n;
cin >> n;
//이동 횟수 계산
//크기가 매우 커서 long 형에 담을 수 없음
vector<long> results;
results.push_back(0);
for (int i = 0; i < n; i++) {
//값 연산
for (int j = 0; j < results.size();j++) {
results[j] *= 2;
if (j == 0) {
results[j] +=1;
}
}
//10의 자리수가 넘어가면 10의 자리를 다음 자리로 더해줌
for (int j = 0; j < results.size();j++) {
int next = results[j] / 10;
results[j] %= 10;
if (next <= 0) continue;
if (results.size() <= j + 1) {
results.push_back(next);
}
else {
results[j+1] += next;
}
}
}
//비용 출력
for (int i = results.size() - 1; i >= 0 ;i--) {
cout << results[i];
}
cout << "\n";
if(n > 20){
return 0;
}
//하노이 타워 출력
hanoi_tower(1, 3,n);
return 0;
}다른 알고리즘 문제는 아래 링크에서 풀어보실 수 있습니다.