(Python/🥈1)백준 알고리즘 1914번: 하노이 탑

 

문제 바로가기 

백준 알고리즘 하노이 탑

 

문제:

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 6 초 128 MB 27752 5855 4501 23.893% 문제 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

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

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5개인 경우의 예시이다.

하노이탑

입력:

 

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

출력:

 

첫째 줄에 옮긴 횟수 K를 출력한다. N이 20 이하인 입력에 대해서는 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다. N이 20보다 큰 경우에는 과정은 출력할 필요가 없다.

풀이:

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')


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

def hanoi(n,i,j,via):
    if n == 1:
        print(i,j)
    else:
        hanoi(n-1,i,via,j)
        print(i,j)
        hanoi(n-1,via,j,i)
print(2**K -1)
if K<=20:
    hanoi(K,1,3,2)

 

 하노이탑 

i 는 지금위치, j는 목적지, via는 경유지

첫 번째  장대에서 세 번째 장대로 옮기려고 한다.

 

탈출 조건은 

원반이 1개 있을때 목적지로 옮기고 끝내면 된다.

 

else: 문 안에 하나씩 보면 

1. 맨 아래 원판 빼고 경유지로 다 옮긴다.

2. 맨 아래 원판을 마지막 목적지로 옮긴다.

3. 맨 아래 원판 뺀거 모아둔 경유지에서 목적지로 옮긴다.