[알고리즘 기본] 하노이탑 알고리즘

 

 

 

 

1. 하노이탑 알고리즘 원리

---

 

하노이탑은 재귀를 이용한 대표적인 알고리즘으로 알려져 있다.

 

출처 : 칸아카데이

 

 

총 3개의 기둥이 존재한다. 주어진 n개의 원판을 다른 기둥으로 옮기는 것을 말한다.

이때 몇 가지 규칙들이 존재한다.

 

• 한 번에 딱 한 개의 원판만 이동할 수 있다.
• 옮겨진 원판은 무조건 맨 위에 올라간다.
• 맨 위에 있는 원판만 옮길 수 있다.
• 크기가 큰 원판은 작은 원판 위로 올라갈 수 없다.

 

 

하노이탑을 3번째 기둥으로 옮기는데 필요한 총횟수는 "2^n - 1" 번이다.

 

예를 들어 3개의 원판을 옮긴다고 생각해보자.

출처 : 칸아카데미

A에 있던 3개짜리 기둥을 C로 B로 옮기는 과정이다.

우선 3번 원판을 옮기기 위해서는 위에 있던 1번과 2번 원판을 C로 옮겨야 한다.

 

• 1번 원판을 A에서 B로 이동
• 2번 원판을 A에서 C로 이동
• 1번 원판을 B에서 C로 이동

 

위와 같이 3번에 과정을 거쳐야 위에 있는 두 개의 원판을 옮길 수 있다.

3번 원판을 옮기기 위해 2개짜리 기둥을 옮기는 문제를 푼 것이다.

바로 재귀적으로 해결한 것이다.

 

3개의 원판을 옮기기 위해 2개 원판까지 옮기는 하위문제를 해결했다.

만약에 n개의 원판이 주어진다면 n-1개의 원판을 옮기는 하위문제를 해결한 것이다.

 

다시 3개의 원판을 옮기는 과정을 살펴보자.

 

 

출처 : 칸아카데미

 

이제 C에서 B로 2개의 원판을 옮겨야 한다.

 

• 1번 원판을 C에서 A로 이동
• 2번 원판을 C에서 B로 이동
• A에 있던 3번 원판을 A에서 B로 이동

 

2개의 원판을 옮기기 위해서는 총 3번의 옮기는 횟수가 필요하다.

재귀적으로 3개의 원판을 옮기기위해 2개의 원판을 옮기는 방식을 불러 해결하고

3번 원판을 1번 옮기기 때문에 총 7번의 이동 횟수가 필요했다.

 

2^3 - 1 = 7
2^n -1

 

 

 

 

2. 하노이탑 알고리즘 예시 코드(JS)

---

 

백준 알고리즘 문제 11729번

11729번: 하노이 탑 이동 순서

원판을 옮긴 횟수,

원판의 이동 과정을 출력하는 문제였다.

 

 

node.js로 숫자를 입력받기 위한 코드는 생략했다.

let answer = '';
let count = 0;
function hanoi(n, from, other, to) {
    if (n === 0) return;

	// n-1개의 원판을 남은축인 other로 옮김
    hanoi(n - 1, from, to, other);
    
    // 마지막에 있는 원판을 목적지로 이동
    answer += `${from} ${to}\n`
    count ++;
    
    // other축으로 옮겼던 n-1개의 원판을 to로 옮김
    hanoi(n - 1, other, from, to);
    return `${count}\n${answer}`;
}

console.log(hanoi(n, 1, 2, 3))

 

n = 원반의 개수

from = 원반이 현재 있는 축

to = 원반을 옮기려고 하는 축

other = 남은 축

 

 

위에서 설명했던 거처럼 원판들을 옮기려면 재귀적으로 함수를 불러와서 해결해야 한다.

원판의 개수가 0이면 아무것도 없이 return 시키는 조건을 추가한다.

원판을 옮길 때마다 count가 1씩 올라갈 수 있게 해 주고

원판이 from에서 to로 옮겨질 때의 이동 과정을 answer에 추가해준다.

마지막으로 count와 answer를 return 하고 출력하면 끝이다.

 

 

 

계속해서 불러낸다는 말이 어쩌면 헷갈릴 수 있지만

한 번 이해하면 여기저기 활용할 수 있다는 생각이 든다.