[알고리즘] 하노이의 탑 - javascript

출처: https://shoark7.github.io/programming/algorithm/tower-of-hanoi

 

A에 있는 모든 원반을 B로 옮기는 횟수의 최소값을 구하는 알고리즘

 

• 제한조건
  • 작은 원반 위에 큰 원반이 올라갈 수 없다.
  • 한 번에 원반 하나만 옮길 수 있다.

 

---

🔑 설명

 

얄팍한 코딩사전님의 영상이 큰 도움이 되어 가져왔다.

아래 영상을 시청하고 설명을 읽으면 이해가 쉽다.

 

 

 

 

 

출처: 얄팍한 코딩사전 [재귀함수는 뭔가요 (Feat.하노이의 탑)]

 

B로 원반을 옮기려면, 가장 큰 원반이 맨 아래로 가는 것이 첫번째 순서다.

 

 

 

이게 가능하려면 그 위 원반들이 C로 옮겨져야 한다. 그래야 맨 아래 원반을 B로 옮길 수 있기 때문이다.

그들을 C로 옮기는 과정은 다시 위 과정을 반복한다.

 

 

 

위 과정과 똑같이 맨 아래 파란색 원반을 목적지로 옮기는 것이 우선이다.

(보라색 맨 아래 원반을 없다고 생각하면 쉽다)

 

 

 

그러려면 위쪽 원반이 B에 순서대로 쌓여야 한다. 그래야 파란색 원반을 옮길 수 있으니까!

여기서 재귀적 성격을 찾아 볼 수 있다. fnc(n)에서 fnc(n-1)을 호출할 수 있는 패턴이 보인다.

이 과정을 거꾸로 돌려, 작은 것부터 옮기는 것부터 해본다고 생각하면 아래와 같다.

 

 

 

B와 C를 번갈아가며 원반을 옮겨주다가 마지막 도착점에 모두 쌓아준다.

원반 총 갯수가 홀수냐 짝수냐에 따라 맨 처음 원반을 도착점에 놓을 것인가, 경유점에 놓을 것인가가 결정된다.

 

 

---

📝 구현

 

이동하는 경로를 출력하는 코드는 아래와 같다.

function hanoi(num, from, to, via) { // 1
    if(num === 0) return; // 2
    hanoi (num - 1, from, via, to); // 3
    console.log(`${from}번에서 ${to}로 옮긴다.`);
    hanoi (num -1, via, to, from) // 4
}

 

1. (인수로 전달) num = 원반의 갯수 / from = 출발점 / to = 도달점 / via = 경유점
2. 재귀함수의 base case : 옮길 원반이 0개라면 재귀 종료
3. 맨 아래 뺀 모든 원반은 from에서 via로 옮김
4. 원반들 다시 via에서 to로 옮김

 

위 코드는 옮기는 과정을 출력하는 코드라 생략되어 있지만,

필요하다면 맨 아래 원반을 옮기는 과정을 console.log 자리에 구현해야 한다.

 

---

예시 문제

 

[프로그래머스 Lv2 '하노이의 탑']

하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.

 

1. 한 번에 하나의 원판만 옮길 수 있습니다.
2. 큰 원판이 작은 원판 위에 있어서는 안됩니다.

하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.

1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.

 

제한사항

• n은 15이하의 자연수 입니다.

---

풀이

function solution(n) {

    let answer = [];

    function hanoi(n, from, to, via) {
        if(n === 1) answer.push([from, to]);
        else {
            hanoi(n - 1, from, via, to);
            answer.push([from, to]);
            hanoi(n - 1, via, to, from);
        }
    }

    hanoi(n,1,3,2);
    return answer;
}

 

 

---

참고

https://www.youtube.com/watch?v=aPYE0anPZqI

https://shoark7.github.io/programming/algorithm/tower-of-hanoi