[백준 11729] 재귀함수로 하노이탑 이동하기

나에게 혼란을 줬던 문제다.

직접 그려봐도 알 것 같은 느낌만 주고 전혀 모르겠던 문제.

재귀는 BFS/DFS로 가는 길에 얼른 풀어보고 끝내려고 했으나 난관이었다.

하지만 그만큼 중요하고 기본적인(?) 문제다.

 

코드를 보기 전에 문제 해결 방법을 먼저 이해하려고 본 유튜브 영상이다.

영어 영상들 사이에서 고마운 영상이었다. (문제 규칙을 이해했다면 3:37부터, 근데 앞부분 설명이 재밌음)

하지만 영상을 두 번 봐도 내 머리로는 정확히 이해가 안 돼서 바로 코드를 봤다.

---

def hanoi(n, start, end):
    if n==1:
        print(start, end)
        return
    hanoi(n-1, start, 6-start-end)
    print(start, end)
    hanoi(n-1, 6-start-end, end)

n = int(input())
print(2**n-1)
hanoi(n,1,3)

 

답은 이렇다.

사실 아직도 제대로 이해한 건 아니다.

다만 이동 횟수가 이렇게 간단할 줄이야. 그려보고서도 몰랐다.

이동 횟수는 2**n-1이고 이동경로는 함수 내 print()로 출력한다.

 

start : 이동할 원판이 있는 장대 (현재 장대)

end : 이동할 장대

그러니까 start 맨 위의 원판이 end로 이동되는 것이다.

여기서 제일 이해하기 힘들었던 6은 장대 번호를 다 더한 1+2+3이고, 6-start-end는 두 장대 외의 나머지 장대 번호를 표현한 것이다.

 

return은 꼭 필요하다. 없으면 에러 난다. (궁금해서 지워봄)

return 0을 하던, 100을 하던, 문자열을 쓰던 상관은 없지만 어쨌든 꼭 필요하다.

---

이 문제는 비슷하거나 같은 문제로 여러 번 복습해야겠다..