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

어떤 분이 통곡의 하노이 탑이라고 적었던데 동의한다.

나는 왜 이 문제가 그 어떤 문제보다 이해가 안 되었을까.. 

다행히 널리 알려진 문제라 설명이나 풀이가 많아 엄청 많이 찾아보고 각 설명의 핵심 포인트가 모여 이해 가능하게 정리되었다. 

 

처음 접한 설명

https://blog.encrypted.gg/943?category=773649 

[실전 알고리즘] 0x0B강 - 재귀

 

1. 재귀에 대해 다시 생각하자. 재귀는 절차지향적인 연산흐름과 떨어뜨려놓아야 한다. 사고를 바꿔야 쉽게 다가올 것.

2. 1개가 가능하고, 1+1개가 가능하다면 전부 가능하다고 인식한다. 즉, n개가 가능하고, n + 1 개가 가능하면 무한의 n개는 모두 해당 조건을 성립한다고. 

3. 대신 재귀 함수를 풀 때는 3가지를 명심해야 한다.

    1) 함수의 정의 (인자를 뭘로 받을 지, 해당 함수는 어디까지 수행하고 마치는지)

    2) base condition: 재귀함수 종료 조건,

    이 두 개가 명확하지 않고 틀리면 무한 루프로 빠질 수 있다.

 

 

두 번째 열 시간 붙들고 계셨다는 그 통곡 분.

https://data-jj.tistory.com/34

백준 11729번 : 통곡의 하노이 탑 (feat. python)

: 그림을 통해 더 구체적인 재귀과정을 묘사하셔서 print시점에 대한 이해가 되었다. 

언제 이동 과정을 그려내게 해야할 지 감이 안 잡혔는데 이걸 보고 print위치가 어느 순서가 맞는지를 느꼈다.

 

 

세 번째 6-start-end 의 아리송함을 정리해준 

https://ko.khanacademy.org/computing/computer-science/algorithms/towers-of-hanoi/a/towers-of-hanoi-continued

하노이의 탑 (2) (개념 이해하기) | 알고리즘 | Khan Academy

: 왜 6-a-b인지 이해가 안 갔다. 처음에. 하노이탑 문제 자체를 덜 이해한 상태였던 것이다.

: n으로만 생각했을 때, 무조건 (n-1, 1, 2), (1, 1, 3), (n-1, 2, 3)이 고정이라고 생각했다. 그런데 위의 풀이도 그렇고 답도 그렇고 그게 아닌 과정이 섞여있는데,

: 해당 설명에서 ' . 다시 한번 말하지만 두 개의 원반을 꼭 축 A에서 축 B로 옮기지 않아도 됩니다. 축 A를 나머지 축으로 이용하고 축 B에서 축 C로 옮겨도 됩니다. 원반 1을 축 B에서 축 A로 옮긴 후 원반 2를 축 B에서 축 A로 옮기고 마지막으로 원반 1을 축 A에서 축 C로 옯깁니다. 원반 1과 2를 특정 축에서 다른 축으로 3단계만에 옮길 수 있다는 것에 동의하시나요? ("네"라고 해 주세요) ' 라고 한 것에서 내가 착각하고 있던 포인트를 알았다. 

 

네 번째 함수 동작과정

https://www.youtube.com/watch?v=FYCGV6F1NuY 

 

 

다섯번 째. 하노이탑 이동횟수

https://lazypazy.tistory.com/55

[백준] 11729번: 하노이 탑 이동 순서

 

def hanoi(n, start, end):
    if n > 1:
        hanoi(n-1, start, 6-start-end)
    print(start, end)
    if n > 1:
        hanoi(n-1, 6-start-end, end)
n = int(input())
print(2**n - 1)
hanoi(n, 1, 3)

 

 

이제는 이해는 한 것 같은데 하도 끙끙대서 아직까지도 내가 이해했는지도 의심스럽다.

재귀 문제를 많이 풀어보며 더 생각을 명확히 해야겠다.