[1914] 하노이 탑

1914번: 하노이 탑

 

www.acmicpc.net

🤔 문제 설명

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다.

각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

 

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

 

🤨 제한 사항

• 첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 100)이 주어진다.

• 첫째 줄에 옮긴 횟수 K를 출력한다. N이 20 이하인 입력에 대해서는 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다. N이 20보다 큰 경우에는 과정은 출력할 필요가 없다.

 

😀 입출력 예

입력	결과
3	7 1 3 1 2 3 2 1 3 2 1 2 3 1 3

 

👩‍🔧 사용 메서드 및 속성

sys.stdin.readline()	사용자로부터 한 줄의 입력을 받습니다.
split()	문자열을 나눠서 배열로 반환합니다.
math.pow(a,b)	a값에 대해 b만큼 거듭제곱 연산을 수행합니다.

 

👩‍🏫 어떻게 풀어요?

통곡의 벽

 

하노이 탑은 알고리즘 초보자들이 부딪히는 통곡의 벽과도 같습니다. 많은 사람들이 재귀 함수를 이해할 때 하노이 탑을 만나버리는 바람에 좌절하곤 하는데요. 이렇게 프로그래머를 좌절시키는 문제이지만, 마스터 한다면 재귀 함수는 다른 알고리즘에서도 무리없이 잘 사용하실 수 있을거에요.

 

그래서 오늘은 하노이의 탑을 뽀사버릴 작정으로 한번 원리 부터 차근차근 알아보도록 하겠습니다!

 

 

 

🤔 하노이의 탑이란?

하노이의 탑 (출처: 위키백과)

하노이의 탑은 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있으며, 왼쪽의 모든 원판을 맨 오른쪽의 기둥으로 옮기는 퍼즐입니다. 옮길때는 한 번에 하나의 원판만을 옮길 수 있고, 그 과정에서 큰 원판이 반드시 작은원판보다 밑에 있어야 합니다.

 

 

😎 원판이 하나인 경우

 

맨 왼쪽을 A 기둥, 가운데 기둥을 B 기둥, 끝의 목적지 기둥을 C 기둥이라고 하겠습니다.

원판이 하나인 경우 A -> C로 가기 위해서는 어떻게 해야할까요?

그냥 단순히 A에서 C로 바로 옮기면 되겠죠?

 

    if disk == 1 :
        print("%d %d" % (start, end))
        return

그렇다면 위의 코드를 유도 할 수 있습니다. 원반이 하나인 경우는 바로 C에다가 꽂아버릴 수 있으니까요!

그러므로 원반이 하나일 때, 시작 기둥과 현재 목표 기둥을 print() 해주면 깔끔하게 경로가 나오겠죠?

 

 

😎 원판이 둘인 경우

 

원판이 2개인 경우는 하나인 경우보다 움직임이 많아집니다.

 

1. 1번 원판을 A에서 B로 옮긴다.

2. 2번 원판을 A에서 C로 옮긴다.

3. 1번 원판을 B에서 C로 옮긴다

 

여기서 알 수 있는 하노이 탑의 특징은 다음과 같습니다.

 

1. 1번의 원반을 C로 옮기기 위해서는 일단 2번 원반을 C로 옮겨야 합니다.

 

2. 그러기 위해서는 1번 원반을 A에서 B로 옮깁니다. 이때 1번은 3번을 갈 수가 없습니다. 우리는 최소 경로를 찾는 것이고, 따라서 1번 원반이 C에 가기 위해서는 우선 2번 원반을 C로 옮겨야 합니다. 그래서 1번 원반의 현재 목표 기둥은 C 기둥이 아니라 B 기둥이 됩니다. 만약 1번 원반의 목표 기둥이 C가 된다면 최소 횟수의 경로로 옮길 수 없습니다.

 

3. 2번 원반을 A에서 C로 옮깁니다.

 

4. 1번 원반을 B에서 C로 옮깁니다.

 

 

 

😎 원판이 셋인 경우

 

원반이 3개인 경우는 훨씬 더 경우가 많아집니다.

 

1. 1번 원반을 A에서 C로 옮깁니다.

2. 2번 원반을 A에서 B로 옮깁니다.

3. 1번 원반을 C에서 B로 옮깁니다.

4. 3번 원반을 A에서 C로 옮깁니다.

5. 1번 원반을 B에서 A로 옮깁니다.

6. 2번 원반을 B에서 C로 옮깁니다.

7. 1번 원반을 A에서 C로 옮깁니다.

 

이 과정을 차근차근 풀어보겠습니다!

 

1. 1번과 2번 원반이 C로 옮겨지기 위해서는 3번 원반이 C로 옮겨져야 합니다. 그러면 어떻게 해야할까요? 바로 1번과 2번 원반이 전부 B에 있다면 3번 원반을 C로 옮길 수 있겠죠? 4번 그림을 봐주세요. 1번과 2번 원반이 B 기둥에 위치하는걸 볼 수 있습니다. 즉, 1번과 2번 원반은 C로 가기 위해서는 목표를 B 기둥으로 삼되. C 기둥을 경유해야 합니다.

 

2. 1번과 2번 기둥이 B로 옮겨졌다면, 3번 원반은 거저먹기식으로 바로 C로 옮길 수 있습니다.

 

3. 그렇다면 다시 1번 기둥이 C로 옮겨지기 위해서는 어떻게 해야할까요? 당연히 2번 기둥이 C로 옮겨져 있어야겠죠. 그럼 1번 기둥을 A기둥으로 옮기고 2번을 C로 옮긴 다음 1번을 A로 옮기면, 3개의 원반이 짜잔 하고 C 기둥에 모두 모여 있는 것을 볼 수 있답니다.

 

 

 

😵 유도

3개의 원반을 옮길 때 유심히 보시면 뭔가 규칙성이 보이실거에요. 안 보이신다구요?

 

3번째 원반이 C로 가기 위해서는 1번과 2번 원반의 목표를 C가 아니라 B로 설정해야 된다고 말씀드렸습니다.

그렇다면,

 

def alg(disk, start, end, middle) :
 
    alg(disk - 1, start, middle, end)
    return
 

이런 식으로 코드를 유도해 볼 수 있겠죠? 왜냐하면 원판이 1개가 아니라면 모든 기둥을 전부 다 사용해야 하고, 3번을 옮기기 위해서는 3개에서 1개가 줄어든 2개만 A 기둥에서 C기둥을 거쳐서 중간의 B 기둥으로 옮기면 되니까요!

 

 

하지만 이것만 가지고는 충분하다고 할 수 없죠.

아까 3개의 원반을 옮길때  1번과 2번 원반이 B에 있다면 3번 원반을 C에다가 꽂을 수 있다는 것을 보여드렸죠?

 

def alg(disk, start, end, middle) :
 
    alg(disk - 1, start, middle, end)
    print("%d %d" % (start, end))
    return
 

 

👾트리스티의 답

import sys
import math
 
def alg(disk, start, end, middle) :
    if disk == 1 :
        print("%d %d" % (start, end))
        return
 
    alg(disk - 1, start, middle, end)
    print("%d %d" % (start, end))
    alg(disk - 1, middle, end, start)
 
    return
 
 
n = sys.stdin.readline().split()
print(int(math.pow(2, int(n[0]))) -1 )
alg(int(n[0]), 1, 3, 2)
 

 

※ 잘못된 정보가 있거나 수정사항이 있다면 댓글로 남겨주세요!