알고리즘 - 재귀 알고리즘(2)

재귀 알고리즘 중 대표적인 하노이 탑을 보겠습니다.

 

일단 3개의 원반을 1번 기둥에서 3번 기둥으로 옮긴다고 했을 때 순서는

 

1번 원반을 1기둥에서 3기둥으로

2번 원반을 1기둥에서 2기둥으로

1번 원반을 3기둥에서 2기둥으로

3번 원반을 1기둥에서 3기둥으로

1번 원반을 2기둥에서 1기둥으로

2번 원반을 2기둥에서 3기둥으로

1번 원반을 1기둥에서 3기둥으로 

이렇게 총 7번 옮깁니다.

 

이걸 크게 3개로 묶어서 생각하면

1,2번 원반을 1기둥에서 2기둥으로

3번 원반을 1기둥에서 3기둥으로

1,2번 원반을 3기둥으로 옮기는 것으로 생각할 수 있습니다.

 

아래는 위 생각을 코드로 만든 것입니다.

def move(no, x, y):
    if no > 1:
        move(no - 1, x, 6 - x - y)

    print(f'원반 [{no}]을(를) {x}기둥에서 {y}기둥으로 옮깁니다.')

    if no > 1:
        move(no - 1, 6 - x - y, y)

n = int(input('원반의 개수를 입력하세요.: '))
move(n, 1, 3)

 

6 - x - y에서 6은 기둥 번호의 합으로 6 - x - y로 중간 기둥 값을 구할 수 있습니다.

 

위 예시 처럼 3개의 원반을 옮긴다고 생각했을 때, move(3, 1, 3)이 처음 들어가면 아래 처럼 됩니다.

def move(3, 1, 3):    

    if no > 1:
        (1)move(2, 1, 2)

    (2)print(f'원반 [3]을(를) {1}기둥에서 {3}기둥으로 옮깁니다.')

    if no > 1:
        (3)move(2, 2, 3)

 

이 때, 첫 if 문으로 (1)move(2, 1, 2)이 먼저 실행하고 이것은 다시

 

(1)move(1, 1, 3)

(2)print(f'원반 [2]을(를) {1}기둥에서 {2}기둥으로 옮깁니다.') 

(3)move(1, 3, 2)

 

이렇게 표현이 되고

 

다시 (1)move(1,1,2)로 들어가게 되면 no 값이 0보다 작아지기 때문에 2개의 if문은 작동하지 않고

print(f'원반 [1]을(를) {1}기둥에서 {3}기둥으로 옮깁니다.')

이 문구가 처음으로 출력됩니다.

 

(1)move(1, 1, 2)가 끝났기 때문에

(2)print(f'원반 [2]을(를) {1}기둥에서 {2}기둥으로 옮깁니다.') <-- 이 문구가 출력이 되고

(3)move(1, 3, 2)도 (1)move(1,1,2)과 같은 이유로 

print(f'원반 [1]을(를) {3}기둥에서 {2}기둥으로 옮깁니다.') <-- 이 문구가 출력이 됩니다.

 

이렇게 되면 첫 번째 묶음인 (1)move(2, 1, 2)가 끝나게 됩니다.

그 다음에 두 번째 묶음인

(2)print(f'원반 [3]을(를) {1}기둥에서 {3}기둥으로 옮깁니다.') <-- 이 문구가 출력이 되고

 

마지막으로 세 번째 묶음인 (3)move(2, 2, 3)가 실행이 됩니다.

세 번째 묶음의 출력은 첫 번 째 묶음과 같은 로직이기 때문에 따로 서술하지 않겠습니다.

 

---

이제 코드를 실행해보면

결과

 

이렇게 총 7번 옮겨지는 것을 확인할 수 있습니다.