1914 하노이의 탑

아이디어

왜 이 문제가 재귀문제인가? 에 집중.
N=2일 때와 N=3일 때를 비교하여 재귀적 구조가 있는지 파악.
직접 다 써봤다.

(N=2)
1 2
1 3
2 3
(N=3)
1 3
1 2
3 2
1 3
2 1
2 3
1 3

그리고 머릿속으로 그림을 그려보면, 금방 다음과 같은 사실을 파악할 수 있음.

N=3의 구조 : 일단 N=2를 1->2로 수행, 그 다음 제일 밑 원판에 대해 1 3은 고정, 그 다음 N=2를 2->3으로 수행

또한 재귀의 최소단위는 N=1임을 알 수 있고, 만들어야 하는 재귀함수에 '어디서' '어디로' 가는지에 대한 정보가 필요함을 알 수 있음.

N=1 -> {어디서} {어디로}를 그대로 출력.

구현

제출 1 (UnboundLocalError)

def hanoi(n, a, b):
    if a == 1 and b == 2:
        c = 3
    elif a == 1 and b == 3:
        c = 2
    elif a == 2 and b == 3:
        c = 1

    if n == 1:
        return f"{a} {b}\n"
    else:
        return hanoi(n - 1, a, c) + hanoi(1, a, b) + hanoi(n - 1, c, b)


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

일단 VSCode에서 테스트했을땐 문제없었으나, 백준에서는 c가 정의되지 않은 상황에 대해 UnboundLocalError 발생.

"아니 그럼 a,b가 정해져야 c가 정해지는데 c는 도대체 어떻게 해야 하나...?"
...결국 GPT 도움받아 c=6-a-b로 정의하면 깔끔하게 해결되는 것 확인.

제출 2 (메모리 초과)

n = int(input())
print(2**n - 1)

def hanoi(n, a, b):
    c = 6-a-b
    if n == 1:
        return f"{a} {b}\n"
    else:
        return hanoi(n - 1, a, c) + f"{a} {b}\n" + hanoi(n - 1, c, b)


print(hanoi(n, 1, 3))

왜 메모리 초과인가?
GPT한테 물어봤을때는 "재귀 호출마다 문자열을 리턴하고 누적하기 때문"이라고 했으나..


(혹시 몰라서 일단 첨부)

사실은... 조건을 보지 못한 것이다...

제출 3 (정답)

n = int(input())
print(2**n - 1)

if n <= 20:
    def hanoi(n, a, b):
        c = 6-a-b
        if n == 1:
            return f"{a} {b}\n"
        else:
            return hanoi(n - 1, a, c) + f"{a} {b}\n" + hanoi(n - 1, c, b)
    print(hanoi(n, 1, 3))

교훈 : 문제, 조건 똑바로 잘 읽자....