[백준/Python] 1914 : 하노이 탑

문제

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

기둥 1, 2, 3이 있고 N개의 원판이 기둥 1에 크기가 큰 순서대로 쌓여있다.

기둥 1의 모든 원판을 기둥 3으로 옮기는 최소 횟수를 구하라.

단, 기둥 위에서는 반드시 큰 원판이 아래에 위치해야 한다.

풀이

원판 이동 출력하기

이 문제는 절차지향적 사고로 풀리지 않는다. 귀납적으로 생각해야 한다.

1번 원판을 기둥 3으로 옮김 -> 2번 원판을 기둥 2로 옮김 -> ... 이런 절차를 정하는 게 아니라 

k번 원판의 움직임이 어떨 것인지 생각해야 한다. 즉 일반식을 도출해야 하는데

일반식을 도출하는 방법은 가장 작은 크기의 경우를 시뮬레이션해보는 것이다.

 

원판 개수는 1~100이므로 가장 작은 경우부터 생각해보자.

 

원판이 기둥 1에 한 개 있는 상황

-> 크기 1인 원판을 기둥 1에서 기둥 3으로 옮기면 됨

 

원판이 기둥 1에 두 개 있는 상황

-> 크기 1인 원판을 기둥 1에서 기둥 2로 옮기기

-> 크기 2인 원판을 기둥 1에서 기둥 3으로 옮기기

-> 크기 1인 원판을 기둥 2에서 기둥 3으로 옮기기

 

N번째 원판은 가장 아래에 깔려있으므로 N번째 원판을 기둥 3으로 옮기기 위해서는 1~N-1번째 원판을 모두 기둥 2로 치운 다음에 옮겨야 한다는 것을 알 수 있다. 그리고 이 원리는 모든 경우 성립되므로 재귀로 풀 수 있다.

 

이동 순서:
n-1개의 원판을 1에서 2로 옮긴다.
1개의 원판을 1에서 3으로 옮긴다.
n-1개의 원판을 2에서 3으로 옮긴다.

 

재귀 알고리즘은 bases condition과 함수 정의만 있으면 된다. 

• base condition : 재귀호출이 중단되는 조건. 모든 입력은 base condition으로 수렴해야 함
• 함수 정의 : 재귀 함수 안에서 일어나는 동작들

이 두 가지에 대한 아이디어를 떠올렸으면 그대로 코드로 구현하면 된다. 

구현 하기:
1. 함수 정의
    1. void func(int n, int a, int b) 원판 n개를 기둥 a에서 b로 옮기는 방법을 출력하는 함수
    2. 함수는 시작 기둥, 도착 기둥도 인자로 받아야 한다.
2. base condition
    1. n=1일 때 (원판 한 개일 때) 원판을 a에서 b로 옮기기
3. 재귀 식
    1. func(n-1, a, 6-a-b) : n-1개의 원판을 a에서 6-a-b로 옮긴다.
    2. print(a, b) : n번 원판을 a에서 b로 옮긴다.
    3. func(n-1, 6-a-b, b) : n-1개의 원판을 6-a-b에서 b로 옮긴다.

 

n=3일 때 decision tree는 위와 같다.

이동 횟수 출력하기

총 이동 횟수의 일반식도 찾아보자.

원판이 n개일 때 이동 횟수를 T(n)이라고 하면 T(n) = 2 * T(n-1) + 1이다. 

T(1) = 1

T(2) = 2*T(1) + 1 = 3

T(3) = 2*T(2) + 1 = 7

T(4) = 2*T(3) + 1 = 15

...

-> 2^n - 1

코드

import sys
n = int(sys.stdin.readline())
def recur(num, start, end): # num개의 원판을 start에서 end로 옮김
    if n>20:
        return
        
    # num==1인 경우 원판 한 개를 옮기는 동작이므로 start에서 end로 옮긴다고 출력함
    if num==1:
        print(start, end)
        return

    # num>1인 경우 3가지 경우를 수행하도록 재귀호출
    recur(num-1, start, 6-start-end)
    recur(1, start, end)
    recur(num-1, 6-start-end, end)

print(2**n-1)
recur(n, 1, 3)

문제 조건에 따라 20을 넘는 경우 출력하지 않아도 된다는 조건을 추가했음