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

BOJ No11729 : 하노이의 탑 이동 순서(파이썬)

 

 

과장 없이 이 문제만 하루 종일 10시간 정도 본 것 같다... 아직도 혼자서 처음부터 풀면 막히지만 계속하다 보면 언젠간

이런 종류의 재귀 함수 문제를 술술 풀 수 있는 경지에 오를 날이 오리라 믿으며 포스팅을 한다.

 

 

---

하노이탑 규칙에 대한 이해는 아래 "파이썬클래스" 님의 영상으로 도움받았다.

www.youtube.com/watch?v=FYCGV6F1NuY

 

---

정답으로서 활용된 코드

def hanoi(n, a, b):
    if n > 1:
        hanoi(n-1, a, 6-a-b)              # 기둥이 1개 이상이면 그룹으로 묶인 n-1개 원판을 
                                          # 중간으로 먼저 다 옮긴다
    print(a, b)

    if n > 1:
        hanoi(n-1, 6-a-b, b)

n = int(input())

print(2**n -1)                               #총 이동해야 하는 횟수
hanoi(n, 1, 3) 

영상에서와는 다르게 '보조' 변수를 따로 선언하지 않았는데 , 전체 3개(1, 2, 3)를 모두 더하고 1,3번 기둥 값을 빼면 나머지 '보조' 변수 역할을 할 수 있다. (6 - a - b)

---

 

정답에서 활용된 재귀 함수의 실행이 머릿속에 그려지지도 않고 이해되지도 않아서 직접 그려보았다.

(n = 3일 때를 가정하고 그렸다.)

 

하노이탑 재귀함수 실행순서

이 함수를 그린것이 위에 그림

 

재귀 함수에 익숙지 않아서 하노이의 탑의 풀이 순서가 영상을 봐도 잘 이해가 되지 않는다면

위 그림을 순서대로 따라가면서 코드를 읽는 것이 이해하는데 조금이나마 더 도움이 될 수도 있다.

전적으로 알린이 입장에서 작성하였다.