자료구조 및 실습 - [2] 재귀 실습문제 - 하노이탑 (2)

재귀문제 중 '하노이의 탑' 문제가 있다. 맨 처음에는 하노이의 탑을 재귀로 푼다는 생각을 하지 못했다.

어느 부분에서 재귀를 찾을 수 있는지 보자.

---

규칙 찾기

먼저 하노이의 탑에는 규칙이 존재한다.

1. 한 번에 한개의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어서는 안 된다.

먼저 원판이 1개인 경우부터 생각해보자.

원판이 1개인 경우의 하노이 탑

원판이 1개인 경우 단순하게 A에서 C로 옮겨주면 된다. 베이스 케이스가 될 것이다!

 

그럼 원판이 두개인 경우를 보자.

원판이 2개인 경우의 하노이 탑

원판이 두개인 경우, 큰 원판이 C에 먼저 깔려야 작은 원판이 그 위에 올라갈 수 있기 때문에 먼저 큰 원판을 C로 옮기기 위해 작은 원판을 B로 옮긴다. 이후 큰 원판을 C로 옮긴다. 마지막으로 작은 원판을 B에서 C로 옮긴다.

 

그럼 원판 3개인 경우도 보자.

 

이번에는 좀 더 큰틀에서 문제를 바라보자.

먼저 가장 큰 원판을 3이라고 하자. 3이 C에 깔려야 나머지 것들이 위로 올 수 있기 때문에, 이를 위해서 3을 제외한 1,2를 B로 옮겨야 한다. B로 옮긴 후 3을 C로 옮긴다. 그리고 B에 있는 1,2를 C로 옮긴다.

다시한번 정리하자면 아래 세단계로 분류할 수 있다.

1. 가장 큰 원판 3을 C의 가장 아래에 깔기 위해, 나머지 것들을 B로 옮긴다. (그림 1 ~ 그림 4)
2. 가장 큰 원판 3을 C로 옮긴다. ( 그림 5 )
3. 나머지 원판을 B에서 C로 옮긴다. ( 그림 6 ~ 그림 8)

가장 큰 원판을 옮기기 위한 전처리 / 가장 큰 원판 옮기기 / 가장 큰 원판을 옮긴 후 후처리

 

만약 원판이 4개가 있다면?

가장 큰 원판 4를 C로 옮기기 위해

1. 나머지 3개의 원판을 B로 옮기고 

2. 가장 큰 원판 4를 C로 옮기고

3. 나머지 원판을 B에서 C로 옮긴다.

 

이를 일반화 하면 다음과 같다.

N개의 원판이 있을 때
1. N-1개의 원판을 B로 옮기고
2. N번째 원판을 C로 옮기고
3. N-1개의 원판을 C로 옮긴다.

근데 1. N-1개의 원판을 B로 옮기고 에서 또 3개의 단계가 실행된다.
1-1. N-2개의 원판을 C로 옮기고
1-2. N-1번째 원판을 B로 옮기고
1-3. N-2개의 원판을 B로 옮긴다.

 

이런 방식으로 진행하다 보면 결국 N번째 원판을 옮기려면 N-1개를 다른 곳으로 옮겨야 하고, N-1번째 원판을 옮기려면 N-2개의 원판을 옮겨야 하고, N-2번째 원판을 옮기려면 N-3개의 원판을 옮겨야 하고... 마지막엔 1개의 원판을 옮기는 재귀가 정의된다.

 

하지만 N번째 원판을 옮길 때와 N-1번째 원판을 옮길때 옮기는 곳이 달라진다. 모든 원판의 최종 목적지는 C로 옮겨가는 것이지만, 그 과정에서 꼭 거쳐가야 하는 기둥이 있기 때문이다. 따라서 함수를 정의할 때 출발점, 목적지, 경유점을 설정해야 한다.

---

함수 정의

def hanoi(N, start, end, via):
    if N == 1: # 옮길 원판이 1개면
        print(start, "->", end) # 시작점에서 도착점으로 이동
    else: # 원판이 2개 이상이면
        hanoi(N-1, start, via, end) # N-1개를 경유지로 옮긴다.
        print(start, "->",end) # N번째 원판을 도착점으로 옮긴다.
        hanoi(N-1, via, end, start) # N-1개를 도착점으로 옮긴다.

위 함수를 정의하고 실행하면 하노이의 탑 문제가 해결된다. 문제를 큰 틀에서 바라봐야 할 것 같다.