[ALGORITHMS]문제 06. 하노이의 탑 옮기기

문제 06 

하노이의 탑 옮기기

원반이 n개인 하노이의 탑을 옮기기 위한 원반 이동 순서를 출력하는 알고리즘을 만들어 보세요.

1. 하노이의 탑

하노이의 탑은 간단한 원반 옮기기 퍼즐입니다.

하노이의 탑에는 크키가 다른 원반이 n개 있고 원반을 끼울 수 있는 기둥이 세 개 있습니다.

하노이의 탑 문제는 어떻게 하면 원반 n개를 모두 가장 왼쪽 기둥(출발점)에서 오른쪽 기둥(도착점)으로 옮길 수 있을까 하는 문제입니다.

단, 하노이의 탑을 옮길 때는 세 가지 제약 사항이 있습니다. 원반은 한 번에 한 개씩만 옮길 수 있고, 각 기둥 맨 위의 원반을 다른 기둥의 맨 위로만 움직여야 합니다.

옮기는 과정에서 큰 원반을 작은 원반 위에 올려서는 안됩니다. 

* 하노이의 탑 규칙

- 크기가 다른 원반 n개를 출발점 기둥에서 도착점 기둥으로 전부 옮겨야 합니다.

- 원반은 한 번에 한 개씩만 옮길 수 있습니다.

- 원반을 옮길 때는 한 기둥의 맨 위 원반을 뽑아, 다른 기둥의 맨 위로만 옮길 수 있습니다.

- 원반을 옮기는 과정에서 큰 원반을 작은 원반 위로 올릴 수 없습니다.

2. 하노이의 탑 풀이

- 원반이 한개 일때

1. 1번 기둥에 있는 원반을 3번 기둥으로 옮기면 끝납니다.(1 -> 3)

한 번만에 원하는 곳으로 원반을 옮겼습니다

- 원반이 두개 일때

1. 1번 기둥의 맨 위에 있는 원반을 2번 기둥으로 옮깁니다.(1 -> 2)

2. 1번 기둥에 남아 있는 큰 원반을 3번 기둥으로 옮깁니다.(1 -> 3)

3. 2번 기둥에 남아 있는 원반을 3번 기둥으로 옮깁니다.(2 -> 3)

세 번 만에 원반 두개를 원하는 곳으로 옮겼습니다.

- 원반이 세개 일때

1. 원반이 두개 일때 방식을 통해서 위에 2개를 2번 기둥으로 옮깁니다( 1->3,1->2,3->2)

2. 1번 기둥에 남아 있는 큰 원반을 3번 기둥으로 옮깁니다.(1 -> 3)

3. 이번에는 2번 기둥에 있는 원반 두 개를 3번 기둥으로 옮깁니다. 비어있는 1번 기둥을 활용하여 원반 2개 일때 방식을 통해 옮깁니다( 2->1, 2->3,1->3)

원반을 한개 씩 전부 일곱 번 옮기면 해결됩니다(3+1+3)

- 원반이 n개 일때

1. 1번 기둥에 있는 n-1개 원반을 2번 기둥으로 옮깁니다(n-1개짜리 하노이의 탑 문제 풀기)

2. 2번 기둥에 남아 있는 가장 큰 원반이 3번 기둥으로 옮깁니다(1 -> 3)

3. 2번 기둥에 있는 n-1개 원반을 3번 기둥으로 옮깁니다(n-1개짜리 하노이의 탑 문제 풀기)

3. 하노이의 탑 알고리즘

* 하노이의 탑 알고리즘

1-a 원반이 한 개면 그냥 옮기면 끝입니다(종료 조건)

1-b 원반이 n개 일때

 1. 1번 기둥에 있는 n개 원반 중 n-1개를 2번 기둥으로 옮깁니다(3번 기둥을 보조기둥으로 사용)

 2. 1번 기둥에 남아 있는 가장 큰 원반을 3번 기둥으로 옮깁니다.

 3. 2번 기둥에 있는 n-1개 원반을 다시 3번 기둥으로 옮깁니다(1번 기둥을 보조 기둥으로 사용)

4. 알고리즘 분석

1층짜리 하노이의 탑 원반을 한번 이동

2층짜리 하노이의 탑: 원반을 세번 이동

3층짜리 하노이의 탑 : 원반을 일곱번 이동

n층짜리 하노이의 탑을 옮기려면 원반을 2^n-1번 옮겨야 합니다

따라서 O(2^n)번이 됩니다