하노이탑 알고리즘 구현 (with Python3)

대학교 과제로 교수님들이 하노이탑 알고리즘을 많이 내준다. (하지만 난 비전공자라 해본적이 없음. 글 쓰면서 오늘 처음 구현해봤다.)

 

하노이탑 알고리즘

하노이탑은 총 3개의 기둥이 존재한다. (그림 참조) 왼쪽부터 1번째, 2번째, 3번째 기둥이라 할때,

1번째 기둥에서 3번째 기둥까지 원반들을 모두 옮겼을때, 최소 걸린 횟수를 구하는 것이 이번 알고리즘의 목표이다. (단, 그림 아래와 같은 조건이 존재)

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

 

목표

• 첫번째 기둥에서 세번째 기둥으로 원반을 모두 (동일한 순서로) 옮긴다.

제약 조건

• 원반은 한번에 하나씩만 옮길 수 있다.
• 옮기는 과정에서 밑에 원반보다 큰 원반이와서는 안된다. (그래서 두번째 기둥을 활용해야 함)

문제 풀이

원반이 1개 일때

1. 첫번째 기둥에서 세번째 기둥으로 옮긴다.

원반이 2개 일때

1. 1번째 원반을 2번째 기둥으로 옮긴다.
2. 2번째 원반을 3번째 기둥으로 옮긴다.
3. 3번째 원반을 3번째 기둥으로 옮긴다.

원반이 3개 일때

1. 원반 2개일때와 같이 1번째 기둥에서 2번째 기둥으로 1번째, 2번째 원반을 옮긴다.(총 3회)
2. 3번째 원반을 3번째 기둥으로 옮긴다.
3. 원반 2개일때와 같이 2번째 기둥에서 3번째 기둥으로 1번째, 2번째 원반을 옮긴다.(총 3회)

 

원반 3개 일때를 보면 알수 있듯이 (원반 2개일때의 값) * 2 에 +1 인 것을 알 수 있다. 따라서,

원반 n개 일때는 총 이동 횟수를 f(n) 이라하면, f(n) = 2 * f(n-1) + 1 라는 것이다.

 

Python3 코드

위 문제풀이를 참조하여 코드를 작성해보자. 아래 코드는 unittest 기반으로 작성했다.

# -*- coding: utf-8 -*-

import unittest


class Exam07(unittest.TestCase):
    """하노이탑 알고리즘"""

    def hanoi(self, k, from_pos, to_pos, aux_pos):
        """하노이탑 알고리즘

        :param k: 원반 개수
        :param from_pos: 출발지 기둥
        :param to_pos: 도착지 기둥
        :param aux_pos: 보조 기둥
        :return: 이동 횟수
        """
        if k == 1:
            print("{}기둥 -> {}기둥".format(from_pos, to_pos))
            return 1

        cnt = self.hanoi(k - 1, from_pos, aux_pos, to_pos)

        cnt += 1
        print("{}기둥 -> {}기둥".format(from_pos, to_pos))

        cnt += self.hanoi(k - 1, aux_pos, to_pos, from_pos)
        return cnt

    def test_hanoi(self):
        print("== 원반 1개 ==")
        self.assertEqual(1, self.hanoi(k=1, from_pos=1, to_pos=3, aux_pos=2))

        print("== 원반 2개 ==")
        self.assertEqual(3, self.hanoi(k=2, from_pos=1, to_pos=3, aux_pos=2))

        print("== 원반 3개 ==")
        self.assertEqual(7, self.hanoi(k=3, from_pos=1, to_pos=3, aux_pos=2))

        print("== 원반 4개 ==")
        self.assertEqual(15, self.hanoi(k=4, from_pos=1, to_pos=3, aux_pos=2))


if __name__ == "__main__":
    unittest.main()

== 원반 1개 ==
1기둥 -> 3기둥
== 원반 2개 ==
1기둥 -> 2기둥
1기둥 -> 3기둥
2기둥 -> 3기둥
== 원반 3개 ==
1기둥 -> 3기둥
1기둥 -> 2기둥
3기둥 -> 2기둥
1기둥 -> 3기둥
2기둥 -> 1기둥
2기둥 -> 3기둥
1기둥 -> 3기둥
== 원반 4개 ==
1기둥 -> 2기둥
1기둥 -> 3기둥
2기둥 -> 3기둥
1기둥 -> 2기둥
3기둥 -> 1기둥
3기둥 -> 2기둥
1기둥 -> 2기둥
1기둥 -> 3기둥
2기둥 -> 3기둥
2기둥 -> 1기둥
3기둥 -> 1기둥
2기둥 -> 3기둥
1기둥 -> 2기둥
1기둥 -> 3기둥
2기둥 -> 3기둥

 

원반이 어떻게 움직이는지 확인하기 위해 위와 같이 구현했지만, 단순히 개수만 구하려면 아래와 같이 하면 된다.

# -*- coding: utf-8 -*-

import unittest


class Exam07(unittest.TestCase):
    """하노이탑 알고리즘"""

...

    def hanoi(self, k):
        if k == 1:
            return 1
        return 2 * self.hanoi(k - 1) + 1

...

if __name__ == "__main__":
    unittest.main()

Reference

• https://thebook.io/006935/part02/ch06/01/