문제

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

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

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

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

그림설명

www.acmicpc.net/problem/11729

  • 입력

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

  • 출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

최종 코드

흠 이동을 몇번해야하는지 횟수는 구할 수 있겠는데 과정을 나타내는 방법은 떠오르지 않았다. 하노이의 탑을 해결하는 원리를 알아야 풀 수 있는 문제였다.

hanoi 함수에서 4가지를 인자로 받는다.

  • n: 옮기는 원판의 개수
  • start: 원판의 출발지
  • by: 원판을 옮기기 위해 보조하는 자리
  • target: 원판의 도착지

이동할 원판이 하나 남았다면 바로 이동하고 함수를 끝낸다.

하나 이상의 원판이 남았다면 마지막 원판을 제외한 모든 원판을 보조 기둥으로 옮긴다.

그리고 마지막 원판을 도착지로 옮기고, 보조기둥에 있던 원판을 다시 도착지로 옮긴다.

재귀함수를 통해 이 과정을 반복하면서 이동한 원판을 ans 배열에 저장하면 원판의 이동 과정을 구할 수 있다.

import sys

def hanoi(n, start, by, target):
    # 원판이 하나 남은 경우 옮기고 종료
    if n == 1:
        ans.append([start, target])
        return
    # 마지막 원판을 제외하고 보조기둥으로 전부 옮긴다
    hanoi(n-1, start, target, by)
    # 마지막 원판을 도착지로 옮긴다
    ans.append([start, target])
    # 보조기둥에 있던 원판들을 다시 도착지로 옮긴다
    hanoi(n-1, by, start, target)

n = int(sys.stdin.readline().strip())
ans = []
hanoi(n, 1, 2, 3)
print(len(ans))
for x in ans:
    print(x[0], x[1])

참고 사이트