하노이 탑

이번에 소개할 알고리즘은 하이노 탑입니다. 재귀를 이용한 알고리즘이며, 워낙 유명해서 재귀를 설명한다고 하면 이 하노이 탑을 예시로 드는 경우가 많습니다.

---

1. 하노이 탑

하노이 탑은 아래 사진과 같이 세개의 기둥에 원반을 꽂는 장난감입니다. 하지만 모든 기둥에는 반드시 큰 원반이 작은 원반보다 아래 와야한다는 규칙이 있습니다.

사진 출처 - http://www.sjtoy.com/m/product_detail.html?brand_uid=2134

초기 상태는 첫 번째 기둥에 모든 원반이 차례대로 쌓여있으며 이 원반들을 세 번째 기둥에 차례대로 쌓아 놓는 것이 하노이 탑의 목표입니다.

 

 

2. 하노이 탑의 작동

다음과 같은 3개 원반을 1번 기둥에서 3번 기둥으로 옮기려고 합니다.

가장 작은 빨간 원반을 3번 기둥으로 보냅니다. 그리고 중간 크기인 주황 원반을 2번 기둥에 보냅니다. 이때, 빨간 원반을 2번에 보내고, 주황 원반을 3번에 보내도 문제가 발생하지 않습니다.

1 2

 

가장 작은 빨간 원반을 2번 기둥의 주황 원반 위에 쌓고 1번 기둥에 있던 가장 큰 노란 원반을 3번 기둥에 쌓습니다. 그리고 빨간 원반을 1번 기둥으로 보냅니다.

3 4

 

그 후 2번 기둥에 있던 주황 원반을 3번 기둥의 노란 원반 위에 쌓고, 1번 기둥에 있던 빨간 원반을 3번 기둥으로 옮기면 하노이 탑 문제에 성공한 것입니다.

5 6

예시로는 3개의 기둥과 3개의 원반을 사용했지만, n개의 기둥, n개의 원반에 대해서도 똑같은 원리로 작동합니다.

 

 

 

3. 하노이 탑 구현

위에서 그렸던 그림대로 하노이 탑을 구현해보겠습니다. 코드가 또 굉장히 간단합니다. 저도 처음에 하노이 탑 문제를 풀 때 굉장히 힘들었었는데, 정답이 이렇게 간단해서 허탈했던 기억이 있네요.

/*
disk는 원반의 갯수, x는 옮기기 시작하는 기둥의 번호, y는 도착 기둥의 번호입니다.
원반은 1번 원반이 제일 작은 원반이고, 숫자가 커질수록 큰 원반입니다.
기둥은 1번이 제일 왼쪽, 가장 큰 번호 기둥이 제일 오른쪽 기둥입니다.
*/

//함수는 disk번 원반을 x기둥에서, y기둥으로 옮기는 일을 합니다.
export const towersOfHanoi = (disk, x, y) => {
    //원반이 하나라면, 과정이 필요없이 바로 옮기면 됩니다.
    if (disk > 1)
        //원반 번호가 1 이상이면 재귀 호출
        towersOfHanoi(disk - 1, x, 6 - x - y);
    }

    console.log("원반[" + disk + "] 이동: " + x + "에서 " + y + "로");

    if (disk > 1) {
        towersOfHanoi(disk - 1, 6 - x - y, y);
    }
};

여기서 잠시 주목해야 하는 부분이 재귀 호출할 때 6-x-y를 인수로 전달하는 과정입니다. 이 식의 의미는 x번 기둥과 y번 기둥의 중간 기둥을 구하는 식입니다. 여기서는 기둥이 3개이며, 기둥 번호가 1, 2, 3번이기 때문에 기둥 번호들을 모두 더하면 6이라는 숫자가 나옵니다. 그래서 6에서 시작 기둥 번호와 도착 기둥 번호를 빼면 두 기둥 사이의 중간 기둥을 구할 수 있게되는 것입니다. 만약에, 기둥이 4개라면 1, 2, 3, 4번 기둥의 번호합인 10-x-y, 5개라면 15-x-y...이런식으로 어떤 기둥이든지 그 사이의 중간 기둥을 구할 수 있습니다.

 

import {towersOfHanoi} from './study-code/recursive/towers-of-hanoi.js';

towersOfHanoi(3, 1, 3);

결과 보면 단계별로 위의 그림과 일치 된게 보이시죠? 이렇게 하노이 탑 문제도 풀어봤습니다.

---

https://github.com/Bam-j/algorithm-study/blob/main/study-code/recursive/towers-of-hanoi.js

GitHub - Bam-j/algorithm-study: 블로그 알고리즘 정리 포스트 코드 수록 + 코딩 테스트 코드 수록