[백준] 9단계 - 11729번 (파이썬) check!

 

11729번

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

 

 

하노이의 탑은 대표적인 재귀 문제이다.

하지만...매번 잊어버리고...매번 어려워한다.

이번에도 혼자 풀다가 엄청 이상하게 풀어버렸다.

내가 돌리면 잘 돌아가고 답도 맞는데 백준에서 돌리면 계속 런타임에러가 떴다.

메모리초과가 뜨기도 하고...ㅎㅎㅎ

망했어요...

 

 

 

결국 위키백과의 도움을 받았다.

매번 볼 때마다 신기한 풀이다.

언제쯤 익숙하게 이런 코드를 생각해낼 수 있을까?

 

 

# 참고: 위키백과 
# https://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%91
# n: 이동시킬 원판 개수
# from_ : 시작 원판, to_ : 도착 원판, via_ : 나머지 원판

def hanoi(n, from_, to_, via_, L=[]):
    if n == 1:
        L.append([from_, to_])
    else:
        hanoi(n-1, from_, via_, to_, L)   # n-1개를 via로 이동
        L.append([from_, to_])            # 가장 큰 것을 to로 이동
        hanoi(n-1, via_, to_, from_, L)   # n-1개를 이제 to로 이동.
    return L

K = int(input())
x = hanoi(K, 1, 3, 2, list())
print(len(x))
for i in x:
    print(i[0], i[1])

 

 

이용한 규칙:

하노이의 탑의 경우, 자신보다 큰 원판을 위에 둘 수 없으므로

맨 마지막 원판(가장 큰 원판)을 도착 위치로 옮기기 위해서는

나머지 원판을 (작은 하노이의 탑 형태로) 다른 위치에 옮겨 놓아야 한다.

 

 

(예) [1,2,3,4]의 원판을 원판1에서 원판3으로 옮긴다면,
[1,2,3]을 원판2에 옮긴 후  →   hanoi(n-1, from_, via_, to_, L)
마지막 4를 원판3으로 옮겨야 한다.  →   L.append([from_, to_])
그리고 나머지 [1,2,3]을 원판2에서 원판3으로 옮기는 과정을 다시 실행한다.
→   hanoi(n-1, via_, to_, from_, L)

그 과정도 동일하게 계속 진행되는데,
이제는 원판2에 있는 [1,2,3] 중 [1,2]를 원판1에 옮긴 후 3을 원판3에 옮겨야 한다.
(이런 식으로 계속 진행되기 때문에 '재귀'로 코딩이 가능한 것 같다...)