[알고리즘] 하노이 탑

Ryan·2023년 12월 30일

알고리즘 재귀알고리즘

알고리즘 PS

목록 보기

2/6

하노이 탑

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

한 번에 한개의 원판만 옮길 수 있다.

가장 위에 있는 원판만 이동할 수 있다.

큰 원판이 작은 원판 위에 있어서는 안 된다.

그림을 통해 살펴보자.
하노이의 탑의 원리

2개의 원판 이동

해당 그림에서는 기둥이 없지만 3개의 기둥이 있다고 생각해보자.

각각의 3개의 기둥을 A, B, C 이고 원판들을 A에서 C로 2개의 원판을 옮기는 방법을 보자.

가장 위에 있는 원판을 B로 이동한다. A->B
두번째 원판을 목적지인 C로 이동한다. A->C
B로 이동 시켰던 첫번째 원판을 C로 이동한다. B->C

총 3번 이동한다.

3개의 원판 이동

위를 바탕으로 3개의 원판을 이동하는 방법도 알아보자.
편의상 원판을 1, 2, 3 으로 수를 부여해 숫자가 작을 수록 위의 원판이라고 생각한다.

A->B
가장 위의 1, 2의 원판을 이동하는 경우이다. 2개의 원판을 이동하는 과정은 A에서 B로 2개의 원판을 옮기는 과정이다.

A->C
A->B
C->B
A->C
마지막 3의 원판을 이동하는 과정이다. 그대로 A->C 만 이동한다.
B->C
B로 옮겼던 1, 2의 원판을 다시 C로 옮기는 과정이다.

B->A
B->C
A->C

3개의 원판을 옮기는 과정을 전부 알아보았다. 총 7번 이동하였다.

결론

위의 2개, 3개의 원판을 이동한 과정을 통해 결론을 도출 해보자.

A->B(마지막 원판을 제외한 원판들을 목적지가 아닌 곳에 이동)

A->C(마지막 원판을 목적지에 이동)

A->C(나머지 원판들을 목적지에 이동)

1번 3번의 경우 나머지 원판들을 특정 위치에 이동시키는 것은 한 위치에서 특정 위치로 이동하는 것으로 생각할 수 있다.
이러한 특성 때문에 재귀함수로 구현이 가능하다.

코드

def hanoi_tower(n, from, others, to, result):
    if n <= 0: return
    hanoi_tower(n-1, from, to, others, result) 	# A->B 이동
    print(A, C)									# A->C 이동  
    hanoi_tower(n-1, others, from, to, result)	# B->C 이동
    
def solution(n):
    answer = []
    hanoi_tower(n, 1, 2, 3, answer)
    return answer