몽상실현개발주의

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

Algorithm PS/BOJ

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

migrationArc 2021. 6. 23. 09:24

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

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

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

 

11729번: 하노이 탑 이동 순서

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

www.acmicpc.net

 

풀이

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

 

마지막 원판을 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])
Comments