BOJ 11729 하노이 탑 이동 순서

문제링크

생각보다 쉽지 않았던 문제.

재귀를 내릴 때 어떤 변수를 함께 내려야 하는 지 항상 생각할 것.

하노이의 탑 같은 경우 링을 옮기려는 기둥의 번호를 재귀 함수의 변수로 사용하는 것이 핵심이다.

def hanoi(n, before, after)

중간 단계로 사용할 기둥은 set을 사용해 구함.

middle = list({1, 2, 3} - {before, after})[0]

나머지는 기초 재귀!

N = int(input())
order = []


def hanoi(n, before, after):
    if n == 1:
        order.append((before, after))
        return 1
    else:
        middle = list({1, 2, 3} - {before, after})[0]
        return hanoi(n - 1, before, middle) + hanoi(1, before, after) + hanoi(n - 1, middle, after)


answer = hanoi(N, 1, 3)
print(answer)
for a, b in order:
    print(a, b)