[BOJ] 11729 / 하노이 탑 이동 순서 / Python 파이썬

[BOJ] 11729 / 하노이 탑 이동 순서 / Python 파이썬

[BOJ] 11729 / 하노이 탑 이동 순서 / Python 파이썬

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

11729번: 하노이 탑 이동 순서

 

풀이

유명한 하노이의 탑 문제를 부할정복으로 푸는 문제이다.

 

마지막 원판을 3번 장대로 옮기기 위한 방법은 다음과 같다.

1. 마지막 원판을 제외한 원판을 2번 장대로 옮기기
2. 마지막 원판을 3번 장대로 옮기기
3. 2번 장대의 모든 원판을 3번 장대로 옮기기

 

그리고 마지막 원판을 옮기기 위해서는 그 이전의 원판들의 작업이 진행 되어야 한다.

 

그러므로 각 원판들의 부분 문제를 해결하여 전체의 문제를 해결 할 수 있다.

 

N = int(input())


def hanoi(n, From, notMove, To):
    if n == 1:
        move.append([From, To])
        return

    hanoi(n-1, From, To, notMove)
    move.append([From, To])
    hanoi(n-1, notMove, From, To)


move = []
hanoi(N, 1, 2, 3)

print(len(move))
for m in move:
    print(m[0], m[1])