[python] 하노이 탑/타워 알고리즘 재귀함수로 구현하기 (Hanoi Tower)

Hanoi Tower

하노이 타워는 3개의 기둥에 원반들을 쌓아 놓고 다른 쪽으로 옮기는 게임이다. 원반은 가장 아래쪽에 있는것이 가장 크고 위로 갈 수록 점차 작아져 전체적으로 원추형의 탐을 이루고 있다. 1에 놓여있는 모든 원반을 3으로 모두 옮겨야 하는데 이때 규칙이 있다. 

 

[규칙]

1. 한번에 하나씩만 옮길 수 있다.

2. 작은 원반위에 더 큰 원반을 놓을 수 없다. 

하노이 타워 예시

 

이렇게 복잡해 보이는 하노이 타워도 재귀함수로 쉽게 구현할 수 있다. 

원반을 직접 옮겨보며 반복되는 규칙을 찾아보자!!

 

 

1. 하노이 타워  반복되는  규칙 찾기 

1) n=1

 

1 ➞ 3 ... 1회

 

2) n=2

 

1 ➞ 2

1 ➞ 3

2 ➞ 3 ... 3회

 

3) n=3

1 ➞ 3

1 ➞ 2

3 ➞ 2

 

1 ➞ 3

 

2 ➞ 1

2 ➞ 3

1 ➞ 3 ... 7회 

 

4) n=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 ... 15회 

 

 

하노이 타워는 이런식으로 계속 반복되게 될것이다. 여기서 우리는 하나의 반복을 찾을 수 있는데. 바로 아래의 그림과 같이 사실 제일큰 원반 1개와 나머지 원반의 이동이 반복된다는 것이다. 이렇게 원반을 2개의 덩어리로 생각할 수 있다는 것이다.

 

만약 n개의 원반을 이동해야 한다고 하면, 문제는  n-1개의 원반을 임시 기둥인 (2)에 옮기고 제일 큰 원반을 우리의 목표 기둥인 (3)으로 옮긴 후 (2)에 있는  n-1개의 원반을 (3)번 기둥에 옮기는 것이다.

 

 

2. 해결방법

그럼 우리의 문제는 3단계로 정의된다. 

첫째, n-1개를 임시 기둥인 (2)로 옮긴다. 

둘째, 제일 큰 원반을 목표 기둥인 (3)으로 옮긴다. 

셋째, 임시 기둥 (2)에 있던 n-1개의 원반을 목표 기둥인 (3)으로 옮긴다. 

 

원반의 이동횟수를 F(n)이라고 할 때, 하노이 타워의 원반이동 횟수는 F(n) = 1 + 2F(n-1)로 나타 낼 수 있다. 

 

그럼 여기서 재귀적으로 문제를 생각하면 

종료 조건은 n=1일때 1 ➞ 3 으로 이동하는 것이 되고 

나머지는 n-1개의 원반을 임시기둥으로 옮길때 한번, 임시기둥에서 목표기둥으로 옮길 때 한번 호출해주면 된다. 

이것을 예제로 다시 살며보면, 이렇게 된다. 

 

3) n=3

 

첫째, 임시 기둥 (2)로 2개의 원반을 옮김

1 ➞ 3

1 ➞ 2

3 ➞ 2

 

둘째, 제일 큰 원반을 목표 기둥인 (3)으로 옮김

1 ➞ 3

 

셋째, 임시 기둥 (2)에 있던 2개의 원반을 목표 기둥인 (3)으로 옮김

2 ➞ 1

2 ➞ 3

1 ➞ 3 ... 7회 

 

4) n=4

 

첫째, 임시 기둥 (2)로 3개의 원반을 옮김

1 ➞ 2

1 ➞ 3

2 ➞ 3

1 ➞ 2

3 ➞ 1

3 ➞ 2

1 ➞ 2

 

둘째, 제일 큰 원반을 목표 기둥인 (3)으로 옮김

1 ➞ 3

 

셋째, 임시 기둥 (2)에 있던 3개의 원반을 목표 기둥인 (3)으로 옮김

2 ➞ 3

2 ➞ 1

3 ➞ 1

2 ➞ 3

1 ➞ 2

1 ➞ 3

2 ➞ 3 ... 15회 

 

3.  하노이 타워 재귀함수로 구현

 

    def hanoi(n, start, temp, end):
        if (n==1):
            print("{start} - > {to}".format(start, end))
            return 
        hanoi(n-1, start, end, temp)
        print("{start} - > {temp}".format(start,end))
        hanoi(n-1, temp, start, end)

 

n : 원반 갯수 

start : 시작 원반 

temp : 임시 원반

end : 목표 원반 

 

hanoi(n-1, start, end, temp) : 첫째, n-1개를 임시 기둥인 (2)로 옮긴다.

print("{start} - > {temp}".format(start,end)) : 둘째, 제일 큰 원반을 목표 기둥인 (3)으로 옮긴다.

hanoi(n-1, temp, start, end) : 셋째, 임시 기둥 (2)에 있던 n-1개의 원반을 목표 기둥인 (3)으로 옮긴다.

 

 

4. 적용문제

문제 : 디스크 𝑛개를 1 번 기둥에서 3 번 기둥으로 옮길 때, 3 번 기둥에 쌓여진 디스크에 변화가 있을 때마다 제일 위에 놓여진 디스크 번호를 출력하는 프로그램을 작성하시오. 단, 3 번 기둥에 놓여 진 디스크가 모두 없어진 경우에는 0 을 출력한다. 예를 들어 위 그림에서 3 번 기둥의 제일 위에 놓여진 디스크 번호는 다음과 같이 변화된다.

 

이 문제는 하노이 타워를 푸는 방식을 동일하지만 우리가 3번에 있는 원반의 이동을 파악하기 위해서 새로운 방식을 생각해야 할 것 같다. 

기존에 우리는 원반의 이동을 print로 출력해서 관찰하였지만 이 문제에서는 원반의 이동을 print가 아닌 새로운 함수를 사용하여 기록하는 편이 원반 번호를 파악하기 쉬울 것 같다. 

 

move_disk 라는 함수를 만들어서 disk(원반)의 움직을 기록해 보자. 

move_disk는 start와 end, target을 입력으로 받는다. 

start, end는 hanoi 함수에서와 같이 1번 기둥 3번 기둥을 의미한다. 

target은 사전 형태의 하노이 타워의 원반 이동을 기록하는 값이다. 

 

move_disk가 호출되면 먼저 end기둥에 들어온 원반을 추가해준다. (3번 기둥 != end기둥 )

여기서 3번 기둥의 원반 흐름을 출력하는 거라면 그냥 3번 기둥이 비어있으면 0, 아니면 원반 번호를 출력해주면되지만,  move_disk는 위에 hanoi함수에 구현되었던 print의 대체다. 즉, 3번 기둥에 원반에 변화가 없더라도  move_disk는 계속 호출이 되는 것이다. 그렇기 때문에 1번 기둥에서 2번 기둥으로 원반이 이동 할 때도, 2번 기둥에서 1번 기둥으로 이동할 때도 3번 기둥의 원반이 계속 출력되게 된다. 

 

우리가 원하는 것은 3번 기둥에 원반의 이동이 있을 때만 기록하고 싶은 것이기 때문에 target에 'disk'라는 key를 추가하여 여기에 3번 기둥의 원반 변화를 순서대로 저장하도록 했다. 

 

# 하노이 타워 알고리즘 
def hanoi(n, start, temp, end, target):
    if (n == 1):
        move_disk(start, end, target)
        return 
    hanoi(n-1, start, end, temp, target)
    move_disk(start, end, target)
    hanoi(n-1, temp, start ,end, target)
    

# disk 움직임을 기록
def move_disk(start, end, target):
    target[end].append(target[start].pop())
    if(target[3]):
        if(len(target['disk']) == 0 or target['disk'][-1] != target[3][-1] ):
            target['disk'].append(target[3][-1])
    else : 
        if(target['disk'][-1] != 0 ):
            target['disk'].append(0)


# testcase
t = int(input())


for i in range(t):
    n = int(input())
    # 원반의 초깃값 설정
    target = {1:list(range(n,0,-1)), 2: [], 3:[], 'disk':[]}

    hanoi(n, 1, 2, 3, target)
    # disk 출력
    print(*target['disk'])

이렇게 move_disk가 호출되고,

end기둥에 원반을 저장하고 ,

3번 기둥이 비어있지 않고 disk에 값이 없거나 원반 흐름에 변화가 있을 때만 'disk'에 값을 추가할 수 있도록 했다. 

disk에 값이 없는 경우를 추가한것은 맨처음 옮겨지는 원반을 기록하기 위해서이다. 

 

 

이렇게 하면 3번 기둥의 원반 흐름을 disk에 한번에 저장해두었다가 출력할 수 있다. 

 

제가 생각한 알고리즘은 이 방법인데 혹시 더 좋은 방법이 있다면 댓글로 많은 조언 부탁드립니다. 

 

reference