[Baekjoon]백준 11729 하노이 탑 이동 순서(골드 5) - Python

문제설명

예제

문제를 살펴보면 하노이 탑을 코드로 작성하여 움직이는 원판 과정까지 출력하면 된다

이전에 자료구조 공부를 하면서 해결한 경험이 있어서 어렵지 않게 해결할 수 있었다

def hanoi_tower(n, fr, tmp, to):
    global cnt
    global result_from
    global result_to
    if n == 1:
        result_from.append(fr)
        result_to.append(to)
        cnt += 1
    else:
        hanoi_tower(n-1, fr, to, tmp)
        result_from.append(fr)
        result_to.append(to)
        cnt += 1
        hanoi_tower(n-1, tmp, fr, to)
    
N = int(input())
cnt = 0
result_from = []
result_to = []
hanoi_tower(N, 1, 2, 3)
print(cnt)
for i in range(cnt):
    print(result_from[i], result_to[i])

코드를 설명하자면 함수는 인자 4개를 입력받는데, n은 옮길 원판 개수, fr은 옮길 대상의 위치(from), 

tmp는 임시로 사용할 위치, to는 이동할 위치이다

n == 1이면 한 개의 원판을 옮기는 것이므로 다른 추가적인 행동 없이 종료하면 된다

< 첫번째 재귀함수 호출 >

n-1개의 원판을 임시 위치로 사용하여 옮긴 후에 하나의 원판이 남으니 해당 원판은 tmp로 옮기면 된다

이해하기 어려울 듯 하니 예시를 들어보자면 A에 N개의 원판이 존재한다고 생각해보자 

C로 옮기려고 한다면 B를 임시 위치로 사용하여 N-1개의 원판을 옮긴 후에 C에 A에 존재하는 하나의 원판을 옮기면 된다

< 두번째 재귀함수 호출 >

A에 존재하는 남은 1개의 원판(가장 큰 크기)을 C로 옮겼으니 이제 B에 존재하는 원판을 C로 옮기면 된다

이러한 과정을 반복하다보면 옮기고자 하는 원판의 개수 - 1개를 하나의 임시 장소(빈 막대)에 옮긴 후에

가장 큰 원판 하나를 목적지로 옮기게 되므로 최종적으로 원하는 하노이탑 코드가 완성된다 

문제에서는 옮긴 횟수와 수행 과정도 출력하라고 하였기 때문에 cnt, result_from, result_to로 선언하여 해결하였다

처음에는 딕셔너리를 활용하려고 했으나 생각해보니 key값이 같으면 값이 바뀌기 때문에 밑의 사진처럼 출력된다

그렇기 때문에 리스트를 두 개 선언하여 해결하였다

result_from에는 옮길 위치, result_to에는 옮긴 곳을 저장하여 for문을 통해 출력하도록 작성하였다