[백준] 11729번 : 하노이 탑 이동 순서 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

11729번: 하노이 탑 이동 순서

 

1. 문제 설명

2. 풀이과정

해당 문제는 우선 하노이 탑의 원판 이동 순서를 알아야 한다.

원판이 1개일 경우에는 그냥 목표 장대로 옮기면 되지만 2개 이상일 때는 마지막 원판을 차례대로 목표 장대에 옮겨야 한다. 이때 마지막 원판을 제외하고 나머지 원판들은 시작 장대와 목표 장대를 제외한 나머지 한 장대에 옮겨놔야 한다.

이러한 하노이 탑의 원판 이동 순서를 파악하고 나서 문제를 해결하면 된다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 첫 번째 장대에 쌓인 원판의 개수를 입력받는다. N = int(sys.stdin.readline())
3. 원판을 이동한 과정을 저장할 리스트를 생성한다. result = list()
4. 원판을 이동할 때 사용할 함수를 생성한다. def hanoi(n, start, end, mid)
5. 함수는 원판의 개수와 원판이 쌓여있는 시작 장대, 원판을 옮길 목표 장대, 원판을 옮기는 과정에서 사용할 중간 장대 순서대로 입력받아진다.
6. 만약 입력받은 원판의 개수가 1개이면 if (n == 1)
7. 원판을 시작 장대에서 목표 장대로 옮기면 된다. result.append([start, end])
8. 반면에 입력받은 원판의 개수가 2개 이상이면 else
9. 마지막 원판을 제외하고 나머지 원판을 모두 중간 장대로 옮겨야 한다. hanoi(n - 1, start, mid, end)
10. 그다음 마지막 원판을 목표 장대로 옮긴다. result.append([start, end])
11. 마지막 원판을 옮겼다면 중간 장대로 옮겨둔 나머지 원판들을 목표 장대로 옮긴다. hanoi(n - 1, mid, end, start)
12. 원판을 옮기는 함수를 활용하여 하노이 탑을 1번 장대에서 3번 장대로 옮긴다. hanoi(N, 1, 3, 2)
13. 원판을 다 옮겼다면 옮긴 횟수를 출력하고 print(len(result))
14. 그 과정 또한 하나씩 출력한다. for i in result: print(i[0], i[1])

반응형

3. 소스코드

import sys

N = int(sys.stdin.readline())

result = list()

def hanoi(n, start, end, mid):
    if (n == 1):
        result.append([start, end])
    else:
        hanoi(n - 1, start, mid, end)
        result.append([start, end])
        hanoi(n - 1, mid, end, start)

hanoi(N, 1, 3, 2)

print(len(result))
for i in result:
    print(i[0], i[1])