백준 11729 : 하노이 탑 이동 순서 (파이썬)

하노이 탑 이동 순서

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	49110	24297	18855	49.114%

문제

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

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

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

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

입력

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

출력

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

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

예제 입력 1 

3

예제 출력 1

7
1 3
1 2
3 2
1 3
2 1
2 3
1 3

---

코드

def hanoi(n):
    if n == 1: return ["1 3"]
    #짝수일때는 오른쪽으로 한칸씩
    if n % 2 == 0:
        tmp = ["1 2", "2 3", "3 1"]
    #홀수일때는 왼쪽으로 한칸씩
    else:
        tmp = ["1 3", "3 2", "2 1"]
    pre = hanoi(n - 1)
    new = []
    for i in range(len(pre)):
        new.append(tmp[i % 3])
        new.append(pre[i])
    else:
        new.append(tmp[len(pre) % 3])
    return new
hanoiList = hanoi(int((input())))
print(len(hanoiList))
print('\n'.join(hanoiList))

해설

문제를 보자마자 규칙이 떠오르지 않아 n을 늘려가면서 하나씩 적어보았다.

이렇게 하나씩 나열해보니 규칙이 보이기 시작했다.

hanoi(1) = 1 3

hanoi(2) = 1 2, hanoi(1) 첫 번째 동작, 2 3

hanoi(3) = 1 3, hanoi(2) 첫번째 동작, 3 2, hanoi(2) 두 번째 동작, 2 1, hanoi(2) 세 번째 동작, 1 3

hanoi(4) = 1 2, hanoi(3) 첫번째 동작, 2 3, hanoi(3) 두 번째 동작, 3 1, hanoi(3) 세 번째 동작,... , 1 2, hanoi(3)의 마지막 

hanoi(n) =
n이 짝수라면 원판을 한칸씩  오른쪽으로 이동하는 사이에 hanoi(n-1) 동작이 추가된다. (3번째 장대일 땐 1번째 장대로)

n이 홀수라면 원판을 한칸씩  왼쪽으로 이동하는 사이에 hanoi(n-1) 동작이 추가된다. (1번째 장대일 땐 3번째 장대로)

 

즉, hanoi(n)을 호출 시 

hanoi(n) -> hanoi(n-1) -> ... -> hanoi(1)까지 거슬러 올라가 hanoi(1)부터 차근차근 만들어 반환하게 된다.