백준 11729번 파이썬 문제풀이(재귀 - 하노이탑 이동 순서)

 

코드

def hanoi(num, from1, to, other):  # 원반갯수,출발지 기둥번호,목적지 기둥번호,나머지 기둥번호
    if num == 0:
        return
    hanoi(num - 1, from1, other, to)  # 1번째 -> 받아온 원반 갯수보다 하나적은 원반들을 목적지가 아닌 곳으로 이동
    move.append([from1, to])  # 2번째 -> 마지막 원반을 목적지로 이동
    hanoi(num - 1, other, to, from1) #3번째 -> 다른 곳으로 옮겼던 원반들을 그 위에 얹는다.


n = int(input())
move = []

hanoi(n, 1, 3, 2) #하노이탑의 함수를 원반 갯수만큼 실행

print(len(move)) #움직이는 횟수 출력

for i in range(len(move)):
    print(move[i][0], move[i][1])

 

-> 개인적으로 재귀문제의 기본중에 기본으로 알려져있는 문제라서 실버2지 그냥 재귀를 일반적으로 다루는 초보 개발자에게 문제를 풀려고 하면 난이도는 중상 이상이라고 생각한다. 이런 깔끔한 재귀를 정답을 보지 않고 생각할 수 있다면 정말 리스펙 한다.. 

 

구글검색해보면 많은 좋은 설명이 있지만 이 유튜브를 참고하면 하노이의탑에 관한 문제를 이해하는데 굉장히 도움이 많이 된다. 다들 참고하면 좋을것 같다.

https://youtu.be/aPYE0anPZqI