파이썬으로 풀어보는 백준 11729번: 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

내 풀이:

n = int(input())
def hanoi(disk, start, mid, end):
    if disk == 1:
        print(start, end)
    else:
        hanoi(disk - 1, start, end, mid)
        print(start, end)
        hanoi(disk - 1, mid, start, end)
print(2**n-1)
hanoi(n, 1, 2, 3)

사실 알고리즘을 전혀 모르겠어서 인터넷의 도움을 받았다. n개의 디스크를 1번 장대에서 3번 장대로 옮기기(n, 1, 2, 3) 위해서는 그 이전에 n-1개의 장대를 2번으로 옮긴 후(n, 1, 3, 2) n번째 디스크를 1번 장대에서 3번 장대로 옮겨야 한다(print(start, end)). 그런 다음 n-1개의 디스크가 쌓인 2번 장대에서 3번 장대로 디스크들을 옮기면 된다(n, 2, 1, 3).

 

정의한 하노이 함수를 분석해보면 hanoi(_, _, _, _)에서 첫 번째 빈칸은 옮겨야할 디스크의 갯수, 두 번째 빈칸은 출발하는 장대, 세 번째 칸은 중간에 거쳐가기만 하는 장대, 마지막이 도착하는 장대로 이해하면 된다. n이 1인 경우에는 하나의 디스크를 원하는 출발 장대에서 도착 장대로 보내주면 되기 때문에 print(start, end)만을 해주면 된다.

 

코딩 과정에 있어서 알고리즘만으로 문제를 푼다는 느낌을 받은 것은 처음이었기 때문에 신선한 충격을 받았다. 문제 풀이 방향이 떠오르지 않는다면 원초적인 알고리즘적 접근을 해보는 것도 좋을 것 같다.