[백준] 11729번: 하노이 탑 이동 순서(Python)

문제 링크

https://www.acmicpc.net/problem/11729

할때마다 까먹는 하노이탑.. 제대로 이해를 못한거같아 밑에 블로그를 보면서 정리해봤다. 

[참고] https://mgyo.tistory.com/185

문제점

N -1개의 원반으로 두번째 막대로 옮겨야한다는 것은 알았음

재귀로 이 문제를 어떻게 풀어낼지에 대해 막힘

 

풀이

재귀란? 같은 형태의 보다 작은 입력을 지닌 자기 자신을 호출하는 것, 재귀적인 호출을 사용하는 함수를 “재귀함수”라고 한다.

그렇다면 이 문제는 재귀의 여지가 있는가?

• hanoi(N): N개의 원판을 ~~~해서 다른 곳으로 옮기기
• hanoi(N-1): N-1개의 원반을 ~~~해서 다른 곳으로 옮기기

이런 식으로 활용 가능하지 않을까?

그럼 hanoi(N) 함수를 반복적으로 사용할 수 있는 곳이 있는가?

3개의 원판이 있는 경우

• 1. 규칙에 따라 3번째 원반을 A -> C로 옮기고 위의 2개의 원반은 B에 이미 꽂혀있어야한다.
• => 즉, hanoi(2)가 필요해보인다.
• 1. 위 그림의 4번째 움직임을 보면, 2개의 원반을 “B”에 꽂은 후 3번째 원반을 “C”로 옮긴다. 이제 2개의 원반을 B -> C로 옮겨야한다. 여기서도 hanoi(2)가 사용된다. 2개의 원반을 C로 옮기기 때문에!

=> 여기서 알 수 있는 것은 hanoi(N)은 2번의 hanoi(N-1) 재귀 과정을 수반한다.

 

출발점, 도착점, 경유점

hanoi(N)함수를 어떻게든 hanoi(N-1)를 활용한 형태로 표현 가능할 것인지의 단서를 찾았다.

하지만 추가적인 정보가 필요하다.

앞서 N 개의 원반을 옮기려면 N-1 함수가 2번 재귀 과정을 거친다.

2번의 재귀과정에서 둘의 도착지가 다르다.

1. 첫번째 재귀: N - 1 개의 원반을 A -> B 로 옮긴다.
2. 두번째 재귀: N - 1 개의 원반을 B -> C 로 옮긴다.

우리의 문제는 출력에서 각 움직임의 출발지, 목적지를 같이 기술해야하기 때문에 이 두 정보를 같이 추적해주어야한다.

따라서 원 함수의 입력이 원반의 개수만 받았다면, 이제는 최소 출발지, 도착지의 변수까지 추가로 받아야한다.

문제의 분해

hanoi(N, start, via, end): Start 에서 via를 거쳐 end로 총 N개의 원반을 운반할 때 각 이동 과정을 출력하자.

 

풀이 코드

n = int(input())
cnt = 0
result = []
def move(start, end):
    global cnt, result
    result.append((start, end))
    cnt += 1
    return


def hanoi(N, start, via, end):
    if N == 1:
        move(start, end)
        return
    else:
        hanoi(N - 1, start, end, via)
        move(start, end)
        hanoi(N - 1, via, start, end)


hanoi(n, 1, 2, 3)
print(cnt)
for item in result:
    print(' '.join(map(str,item)))