파이썬 알고리즘 기초 - 하노이의 탑 (재귀 알고리즘)

하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다.

게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.

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

 

하노이의 탑의 원리(애니메이션)

하노이의 탑 문제는 재귀 호출을 이용하여 풀 수 있는 가장 유명한 예제 중의 하나이다. 그렇기 때문에 프로그래밍 수업에서 알고리즘 예제로 많이 사용한다. 일반적으로 원판이 n개 일 때, 2^n -1(=2의 n승 빼기 1)번의 이동으로 원판을 모두 옮길 수 있다(2^n -1는 메르센 수라고 부른다).

 

위 글은 위키백과에서 가져온 자료입니다. 

 

우선, 하노이의 탑은 재귀 알고리즘을 공부할 때 많이 예로 드는 알고리즘입니다. 

 

그전에 알아야 할 게 있습니다. 

 

1) return으로 함수 중간에서 빠져나오기

 

파이썬에서 함수를 만들 때 마지막에 return 을 해줍니다. 이 때, return 다음에 아무것도 없다면 어떨까요? 

 

위 함수에는 return 다음에 반환값을 넣어주지 않았습니다. 이 때 return 은 어떤 기능을 하는걸까요?

보통 return 을 통해 연산의 결과를 '반환'해주는데 위 함수처럼 아무것도 없을시에는 '함수 중간에 빠져나오도록 하는'

기능을 합니다.

 

solution 함수에 7를 넣으면 빠져나오고 그외의 값을 넣으면 print문이 출력됩니다. 

이처럼 return 만 들어가 있으면 함수 중간에서 빠져나올 때 자주 사용합니다. 보통은 if 와 조합해서 특정 조건일 때 함수 중간에서 빠져나옵니다. 

2) '하노이의 탑' 코드

위키백과에는 파이썬으로 구현한 코드가 있지만 주석이 없습니다. 

마침 '모두의 알고리즘 with 파이썬' 책에 자세한 주석이 나와 있어서 첨부합니다. 

 

함수 안에서 자기 자신을 다시 호출한 것이 보이나요? 

위와 같은 방식때문에 재귀입니다. 

 

n개의 원반이 있을 때 기본적으로 밑에 있을수록 원반의 크기가 큽니다. 제일 아래에 있는 원반이 제일 크겠죠? 

이 원반이 목적 기둥(to_pos)로 가기 위해선 나머지 원반들이 보조 기둥(aux_pos) 로 이동해야 합니다. 이를 위해

첫 번째 재귀 호출

hanoi(n -1, from_pos, aux_pos, to_pos) 

이 나옵니다. 

 

맨 마지막 원반을 제외한 나머지 애들을 보조 기둥으로 보내라는 명령입니다.  

n=2 인 경우를 보죠. 이 때 함수에서는 재귀 호출을 통해 

 

hanoi(2,1,3,2)를 호출하면 

    hanoi(1,1,2,3) # 1번째 재귀 이 때의 결과로 ;   1->2 가 출력 

    print(1,'->',3)  #  실행 결과로 ; 1->3 이 출력 

    hanoi(1,2,3,1) # 2번째 재귀 결과로 ; 2->3 이 출력

 

가 됩니다. 

 

사실, 제가 하노이의 탑을 알고리즘으로 구현하라고 햇을 때, 원반을 변수로 뭐라고 정의해야되지? 기둥은? 

이런 생각을 했는데요. 

 

이 문제의 핵심은 3가지 원기둥을 1,2,3 이라고 정하는데 이 뜻은 시작,보조,목표 기둥 3가지입니다. 

이 기둥 번호들을 통해서 원반이 어떻게 이동되는지를 기둥 번호로 나타내는 것이 하노이의 탑의 핵심입니다. 

 

원반 2개가 1번 기둥(시작기둥)에 있고 이를 3번 기둥(목표 기둥)으로 보내야 될 때 어떻게 원반들을 보낼 것이냐라는 거죠. 

그러면 먼저 작은 원반을 2번 보조기둥에 보내고(1->2), 2번째로 1번 기둥에 있는 큰 원반을 3번으로 보내고,(1->3) 다시 2번 기둥(보조기둥)에 있는 원반을 3번 기둥(목표 기둥)으로 보내주면(2->3) 됩니다. 위 코드와 같죠. 

 

핵심은 제일 큰 원반을 제외한 나머지 원반들을 보조 기둥으로 보낸 다는 것. (재귀로 구현)

그 다음 시작 기둥에 딸랑 혼자 있는 제일 큰 원반이 처음의 목표 기둥으로 간다는 것 (이는 print로 구현)

보조 기둥에 있는 원반들(n-1개의 원반들)은 크기가 작은게 밑에 있고 큰게 제일 위에 있죠? 그러니 그대로 목표기둥으로 

보내면 됩니다.(다시 재귀로 구현) 

 

이게 하노이의 탑 알고리즘의 핵심입니다.

 

저처럼 이런 선입견때문에 하노이의 탑을 코드로 구현하는 걸 보면서 처음엔 아리송해하는 분들이 많이 없으면 좋겠네요 ㅠㅠ 저는 한 번 어떤 선입견을 가지면 그 틀을 쉽게 못 깨는 폐쇄적인 사고의 소유자니깐요...ㅠㅠ 

 

n=3 의 경우는 어떨까요?

 

hanoi(3,1,3,2)

    hanoi(2,1,2,3) # 첫 번째 재귀인데 이 함수도 다시 재귀가 있죠? 들여쓰기로 구분할게요

        hanoi(1,1,3,2)

        hanoi(1,3,2,1)

    print(시작,'->',목표)

    hanoi(2,2,3,1)

        hanoi(1,2,1,3)

        hanoi(1,1,3,2)

 

n=3 인 경우는

유투버 '파이썬 클래스'님의 영상에서 애니메이션으로 설명이 잘 되어있어서 이걸 보면 이해에 도움이 더 될 거 같습니다. 

 

https://www.youtube.com/watch?v=FYCGV6F1NuY&t=302s

이상으로 파이썬으로 구현한 하노이의 탑 알고리즘 구현을 마치겠습니다 :) 

 

 

 

 

 

--참고--

https://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%91

하노이의 탑 - 위키백과, 우리 모두의 백과사전

https://thebook.io/006935/part02/ch06/03-01/

모두의 알고리즘 with 파이썬: 03 하노이의 탑 알고리즘 - 1

https://dojang.io/mod/page/view.php?id=2339

파이썬 코딩 도장: 29.3 함수의 결과를 반환하기