하노이 탑 10 개 - hanoi tab 10 gae

11729번: 하노이 탑 이동 순서

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로

www.acmicpc.net

백준에 있었던 하노이의 탑 이동 순서 문제.

공식만 알면 쉽게 풀 수 있는 문제인 개념이므로 개념을 정리해 보겠다.

하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다.
게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.

1. 한 번에 한개의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어서는 안 된다.

우선 하노이의 탑에서 원판이 n개일 때 원판들의 이동횟수는 다음과 같다. 

1. n = 1, 그냥 하나만 옮기므로 1번
2. n = 2, 3번
3. n = 3, 7번
4. n = 5, 15번

즉, 이동횟수에 대한 점화식은

An = 2*A(n-1) + 1이라고 할 수 있다.

물론 위키피디아 설명에서 말한 것 처럼, 2^n - 1로 생각해도 상관없다. 둘 다 같은 뜻이다.

이동횟수는 알았는데 이동경로는 어떻게 알 수 있을까? 한번 그려보고 규칙을 찾아보자.

n = 2일 때,

1. 1 -> 2
2. 1 -> 3
3. 2 -> 3

n = 3일 때,

1. 1 -> 3
2. 1 -> 2
3. 3 -> 2
4. 1 -> 3
5. 2 -> 1
6. 2 -> 3
7. 1 -> 3

n = 4일 때,

1. 1 -> 2
2. 1 -> 3
3. 2 -> 3
4. 1 -> 2
5. 3 -> 1
6. 3 -> 2
7. 1 -> 2
8. 1 -> 3
9. 2 -> 3
10. 2 -> 1
11. 3 -> 1
12. 2 -> 3
13. 1 -> 2
14. 1 -> 3
15. 2 -> 3

이다.

사실 위 관계로는 내 경우에는 유추하기가 쉽지 않았다.

찾아보니 다음과 같은 매커니즘이였다.

1. A -> B로 n-1개의 원판을 옮긴다.
2. n-1개가 다 옮겨졌다면 A -> C로 1개의 원판을 옮겨놓는다.
3. 후에 B -> C로 다시 n - 1개의 원판을 옮긴다.

위키피디아에서 예시 코드를 확인해 보았다.

#include <cstdio> 
using namespace std; 
void move(int from, int to) { 
     cout << from << " -> " << to << '\n'; 
} 

void hanoi(int n, int from, int by, int to) { 
     if(n == 0) return; 
     hanoi(n - 1, from, to, by); 
     move(from, to); 
     hanoi(n - 1, by, from, to); 
}

출처 : 위키피디아 - https://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%91

위 코드가 예시 코드이다.

void go(int cnt, int from, int by, int to) {
    if (cnt == 1) {
        cout << from << " " << to << "\n"; // 만일 원판이 한 개만 있을 경우에는 바로 3번으로 옮긴다.
    }
    else {
        go(cnt - 1, from, to, by); // 1번 -> 2번으로 n-1개를 옮기기 위한 재귀함수.
        cout << from << " " << to << "\n";
        go(cnt - 1, by, from, to); // 2번 -> 3번으로 n-1개를 옮기기 위한 재귀함수.
    }
}

백문 문제에 맞게 다음과 같이 바꾸었고 거의 흡사하다.

예시로 go(3, 1, 2, 3)을 호출한다면

• go(2, 1, 3, 2) -> go(1, 1, 2, 3) -> "1 3" -> "1 2" -> go(1, 3, 1, 2) -> "3 2" -> "1 3" -> go(2, 2, 1, 3)
• -> go(1, 2, 3, 1) -> "2 1" -> "2 3" -> go(1, 1, 2, 3) -> "1 3"

의 순서로 진행이 된다.

하노이 탑 공식은 유명한 공식이므로 한번 정리해 보았다.

신문은 선생님

[개념쏙쏙! 수학] 하노이 탑, '거듭제곱' 이용해 최소 옮길 횟수 구해볼까

제3의 기둥 이용해 다른 기둥으로 원판을 모두 이동시키는 게임단, 작은 원판 위에 큰 원판 못 올라가원판 3개면 7번 만에 이동하지만 32개면 2³²­-1회 거쳐야 모두 이동

"아빠, 지구의 종말은 정말 올까요?"

기영이가 뭔가 불안해하는 표정으로 아빠 방에 들어왔어요.

"뜬금없이 그게 무슨 말이냐?"

"인터넷 카페에 누가 세상의 종말에 대한 이야기를 올려놓았는데, 말도 안 되는 소리인 줄 알면서도 괜히 마음이 불안하더라고요."

"하하. 그럼 이건 어떠니? 여기에도 지구의 종말에 대한 비밀이 담겨 있는데."

아빠는 기영이에게 그림과 같은 장난감 하나를 보여줬어요.

"이건 하노이 탑이잖아요?"

"그럼 놀이 방법도 알고 있니?"

"이건 원판을 다른 기둥으로 옮기는 놀이잖아요. 옮길 때, 큰 원판이 작은 원판 위로 올라가면 안 된다는 규칙이 있지요."

"잘 알고 있네. 그런데 하노이 탑의 전설에 따르면 탑 모양으로 놓인 64개의 원판을 다른 기둥으로 모두 옮기면 세상의 종말이 온다는 말이 있어."

"예? 64개의 원판을 다른 기둥으로 옮기는 건 누구나 할 수 있는 일 아닌가요? 저도 8개의 원판을 10분도 안 돼서 다 옮길 수 있다고요. 64개면 이것의 8배 정도니까 넉넉잡아 2시간이면 다 옮길 수 있을 텐데요."

"하하. 8개를 10분 안에 옮겼다고 해서 64개도 그렇게 빨리 옮길 수 있을 거라 생각하면 안 되지. 자, 원판 수를 하나씩 늘리며 옮겨보자. 하나일 때는 한 번만 움직이면 되니 넘어가고, 두 개일 때는 빈 두 기둥에 하나씩 옮기고 작은 것을 큰 것 위에 올려놓으면 되니 3번 만에 완료네. 그럼 3개일 때는 몇 번에 옮길 수 있을까?"

"그거야. 7번 만에 옮길 수 있지요."

"잘했어. 그럼 한 번 옮기는 데 1초가 걸린다고 해 보자. 그럼 원판의 수가 많아질수록 걸리는 시간도 늘어나잖아?"

"아. 그러네요. 4개일 때는 15번 움직였으니 15초, 3개 움직였을 때보다 8초나 더 걸리네요."

"그렇지? 그럼 64개의 절반인 32개를 옮긴다면 시간은 얼마나 걸릴까?"

"32개요? 종이로 모양을 만들어서 한번 해 볼까요?"

"직접 해 보겠다고? 네가 정말 1초에 한 번씩 옮긴다 하더라도 살아생전엔 절대 옮길 수 없다는 것만 미리 알아두렴."

"예? 32개의 원판을 절대 옮길 수 없다고요? 그게 무슨 말씀이세요?"

"자. 방금 원판을 4개까지 움직였을 때, 늘어나는 횟수를 잘 분석해 보면 어떤 규칙을 찾을 수 있을 거야. 그 규칙을 찾으면 굳이 32개의 원판을 직접 옮겨보지 않아도 몇 회나 옮겨야 하는지 알 수 있지."

"1회, 3회, 7회, 15회…여기에 어떤 규칙이 있다고요? 잘 보니 원판 하나가 늘어날 때마다 횟수가 2배에 1회가 더해진 수가 되네요?"

"그래. '1, 3, 7, 15'는 각각의 수가 앞 수의 두 배에 1을 더한 값이 된다는 것이지."

(1×2)+1 = 3, (3×2)+1 = 7, (7×2)+1 = 15

"그럼 원판이 5개일 때는 (15×2)+1 해서 31회 움직이면 되겠네요?"

"그래. 시간이 좀 걸리겠지만 정말 그런지 확인해 볼까?"

"아. 정말 31회째에 원판을 모두 옮겼어요. 그럼 32개의 원판을 옮기는 횟수도 이런 방법을 쓰면 되겠네요? 6개일 때는 63회, 7개일 때는 127회, 8개일 때는 255회, 9개일 때는…어휴. 이 방법도 시간이 오래 걸리네요."

"하하. 좀 더 머리를 써 보자꾸나. 1, 3, 7, 15, 31…에 1씩 더해볼래?"

"2, 4, 8, 16, 32…가 되지요. 어? 이렇게 놓으니 점점 2배씩 늘어나는 형식이 되네요?"

"맞아. 2, 2×2, 2×2×2, 2×2×2×2 식으로 2가 거듭해서 곱해지는 형식이지. 이것을 2의 '거듭제곱'이라고 하며 2¹, 2², 2³, 2⁴…으로 표기할 수 있어. 2 위에 있는 작은 수는 2를 몇 번 곱하는지 그 횟수를 나타내는 것으로 '지수'라고 불러. 자. 그럼 지수와 원판의 수가 어떤 관계에 있는지 알 수 있겠지?"

"아! 지수와 원판 수가 똑같아요."

"맞아. 즉, 원판의 수를 n이라는 문자로 놓으면 원판이 n개일 때, 원판을 모두 옮기는 횟수는 2ⁿ－1이 되는 거야. 그럼 이제 원판이 32개일 때 옮겨야 하는 횟수를 구할 수 있겠지?"

"아. 그럼 2ⁿ－1, 즉 2를 32번 곱한 값에서 1을 빼 주면 되겠네요!"

"그래. 2를 32번 곱하는 것도 어느 정도 시간이 걸리니 계산기로 계산해 보렴."

"2곱하기 2곱하기 2…어? 4,294,967,296! 그럼. 42억9496만7295번이나 옮겨야 한다는 건가요?"

"그래. 1년을 초로 계산하면 365일×24시간×60분×60초＝3153만6000초이니 구한 횟수를 1년으로 나누면 4,294,967,295÷31,536,000＝136.1925… 약 136년이 나오지."

"으아. 겨우 32개라고 생각했는데 이렇게나 엄청난 시간이 필요하다니… 그럼 64개는 이보다 더 오랜 시간이 걸리겠죠? 하노이 탑은 오히려 종말은 오지 않을 거라고 예언하는 것 같네요."

[관련 교과]

[함께 생각해봐요]

2, 5, 8, 11, 14…에서 규칙을 찾고 33번째 숫자를 구해 보세요.

풀이: 2부터 3씩 늘어나는 규칙을 가지는 수의 열이에요. 수의 순서를 n으로 놓으면, n이 1씩 커질 때마다 수는 3씩 늘어나야 하므로 3×n이 되겠고, 2에서부터 시작했기 때문에 3×n에서 1을 빼 주면 (3×n)-1이란 식이 나오게 됩니다. 즉, 33번째 수는 (3×33)-1＝98이에요.