BOJ 11729 : 하노이의 탑[python3]

문제

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

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

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

아래 그림은 원판이 5개인 경우의 예시이다.

풀이

문제가 처음에는 하나도 이해하지 못하고, 답을 거의 베끼다 싶이 풀었다. 현재는 문제가 단순하고 재귀를 쓰면 된다는 룰도 이해했다. 먼저 나는 풀이 후에 마지막으로 계속 runtime error가 발생했다. 재귀의 깊이가 얕아서 나오는 문제라고 했는데, 호출 깊이를 더 깊게 하더라도 발생했다. 결국 해결했는데, 문제는 코드의 길이가 길고, 들어오는 변수가 많아서 문제였다. 내 진짜 문제는 중간 출력 부분을 전역변수로 선언한 list에서 추가를 거듭해서 발생하는 문제였다. 하노이 탑에서 계산되는 수는 결국 2**N - 1인데 이것을 공식을 모르면 결국 list에 담고 그 개수를 출력할 수 밖에 없다.(문제의 순서가 그렇게 되어 있음.). 결국 다른 의도로 문제를 풀어야 한다는 것인데 뭐 여튼 풀이는 아래를 참고하는게 더 좋다.

https://stricky.tistory.com/155

파이썬 재귀호출 알고리즘 하노이의 탑 옮기기 #6

문제가 진짜 복잡하지만, 재귀로 풀 수 있는게 더 신기하다.

- 3칸 짜리 하노이 탑 예시 -

1. 주어진 상황에서 제일 위의 파트(1)를 제일 끝단으로 옮긴다. 이후 두 번째 파트(2)를 중간으로 옮긴다.

- 순서 : 2, 3 - x - 1

2. 중간에 2를 올린다.

- 순서 : 3 - 2 - 1

3. 끝 단의 파트를 중간 단으로 옮긴다.

- 순서 : 3 - 1,2 - x

4. 첫 단의 파트를 끝 단에 배치한다.

- 순서 : x - 1,2 - 3

4. 이후, 중간의 파트를 첫 단에 배치하고,

- 순서 : 1 - 2 - 3

5. 중간의 파트를 다시 끝 단에 올린다.

- 순서 : 1 - x - 2,3

6. 다시, 첫 단의 파트를 끝 단에 배치한다.

- 순서 : x - x - 1,2,3

import sys

sys.setrecursionlimit(10**6) # 재귀 호출 깊이를 늘리는 방법

def hanoi(N, from_pos, to_pos, aux_pos):
    if N == 1:
        print(from_pos, to_pos)
        return

    hanoi(N-1, from_pos, aux_pos, to_pos)
    print(from_pos, to_pos)
    hanoi(N-1, aux_pos, to_pos, from_pos)

if __name__ == '__main__':
    N = int(input())
    print(2**N - 1)
    hanoi(N,1,3,2)