[백준 11729번] - 하노이 탑 이동 순서 (javascript)

[11729] 하노이 탑 이동 순서

들어가기 전에

오늘은 백준 골드 5 난이도의 하노이 탑 문제를 자바스크립트로 풀어봤다. 이 문제는 재귀문제로 재귀의 개념과 작동 원리를 이해하고 있어야 한다. 

문제 설명

입력값으로 하노이 탑의 높이인 N이 입력되면 1번 장대에 존재하던 N개의 탑을 모두 3번 장대로 이동시키는 이 문제의 목표이다. 단, 한 번에 하나의 원판만 옮길 수 있으며, 더 작은 원판 위에 더 큰 원판을 올릴 수 없다.

선수 지식

이 문제를 풀기 전에 알아야 할 개념은 아래와 같다.

• 재귀 함수를 구현하는 방법

사용한 함수/메서드

문제 풀이에 있어 핵심 메서드는 아니지만, 결과 출력을 처리할 때 사용했다.

• Array.prototype.join()

아이디어

이해를 돕기 위한 설명

우선 문제에서 주어진 예시 입력값을 가지고 생각해보자. 하노이 탑의 높이가 3인 경우이다. 판은 (빨간색 / 주황색 / 노랑색)으로 구성돼 있다.

 

일단, A에 있는 탑을 전부 C로 옮기기 위해서는 A의 가장 밑에 있는 노랑색 판을 먼저 C로 이동시켜야 한다. 작은 원판 위에 더 큰 원판을 올릴 수는 없으므로, A에는 노란색 판만 남아 있어야 하고, C에는 어떠한 원판도 존재해서는 안된다. 그렇다면 나머지 탑(빨강색과 주황색)은 어디에 있어야 할까? 전부 정렬되어 B 장대에 있어야 한다. 즉 아래 우측의 그림과 같은 상태를 만들어야 한다.

이 상태가 돼야 노란색 판을 C로 이동시킬 수 있다. 자 근데 생각해보자, A에서 B로 (빨간색, 주황색 판)을 이동시키기 위해서는 주황색 판(또 맨 아랫판이네!)부터 (A→B) 로 이동시켜야 한다. 그런데 위에 빨간색 판이 하나 더 있다. 그럼 빨간색 판은 어디로 이동시켜야 할까? 빨간색 판은 (A→B)로 주황색 판이 이동하는 걸 막으면 안되므로 나머지 장대인 C로 이동해야 한다. 빨간색 판을 이동시키고 나면, 이제 주황색 판을 (A→B)로 이동시킬 수 있게된다, 그리고 C에 있는 빨간색 판을 B로 갖고 오면? A에 있는 노란색 판을 C로 이동시킬 수 있게 되는 거다.

 

자 C로 노란색 판을 이동을 시켰으면 이제 B로 옮겨놓은 나머지 탑을 똑같이 맨 아랫판부터 C로 차례차례 갖고 와야 한다. 이 때, B의 주황색 판을 C로 갖고 오기 위해서는 어떻게 해야할까? 위에서 진행했던 방식과 마찬가지로 B(from)의 주황색 판을 C(to)로 (B→C)로 이동시키기 위해서는 나머지 장대인 A(temp)로 주황색 판 위의 탑들을 모두 이동시켜야 한다. 위에 빨간판밖에 없으니 그냥 옮기면 된다!

 

 

💡아하!

A 에서 C로 N개의 탑을 이동시키려면, 먼저 A에서 B로 (1 ~ N - 1)개의 판을 이동시킨 뒤 N번째 판을 C로 이동시켜야 한다. 이 부분에서 재귀함수가 사용되는 것이다.

왜냐면 A에서 B로 (1 ~ N - 1)개의 판을 이동시키려면 먼저 N - 1번째 판이 B로 이동해야 하기 때문에 또 A에서 C로 (1 ~ N - 2) 개의 판을 이동시켜야하기 때문이다. 이 과정은 옮겨야 하는 판의 높이가 1이 될 때까지 계속된다. 이게 base line, 재귀의 탈출 조건이 되는거다.

 

아이디어 정리

위의 글이 너무 기니, 간단하게 정리해보겠다.

 

① 맨 아랫판 위에 있는 걸 모두 목적지도 출발지도 아닌 장대로(temp)로 옮긴다  (1 ~ n-1)의 판
② 맨 아랫판을 목적지로 옮긴다 n번째 판
③ temp로 옮겨 놨었던 나머지 탑을 목적지로 옮긴다 (1~n-1)까지의 판

 

여기서 맨 아랫판 위에 있는 나머지 탑을 이동시키는 과정에서 재귀함수가 쓰인다. 판이 한 개 밖에 남지 않을 때까지 계속 위의 탑을 옮기고, 옮기고,,,, 해야하기 때문이다.

 

 

코드 설명

const fs = require('fs');
const N = +fs.readFileSync('/dev/stdin').toString().trim();

let cnt = 0;
let answer =[];

// 어디서 어디로, 높이가 얼마나 되는 탑을 이동시킬건지!
function hanoiTop(from, to, height) {

    //탑의 높이가 1이라면, 맨 아래 원판만 있으므로 바로 옮겨주면 된다.
    if(height === 1) {
        answer.push(`${from} ${to}`);
        cnt++;
        return;
    }

    //탑의 높이가 2 이상인 n이라면, 맨 아래 원판 위에 있는 탑 (1~n-1)을 우선 옮겨야 한다.
    //어디로 옮겨야 하냐, from과 to가 아닌 다른 판으로 이동시켜야 한다.
    // 1 + 2 + 3 = 6이고, 6에서 from과to의 번호를 빼면 나머지 장대의 번호가 나올 것이다.
    const temp = 6 -  from - to;
    hanoiTop(from, temp, height - 1);

    //위에 쌓인 탑을 다 치웠으면, 맨 아래 위치한 원판을 원하는 곳으로 이동시킬 수 있다.
    hanoiTop(from, to, 1);

    //console.log('탑을 가져온다');
    hanoiTop(temp, to, height - 1);
}

hanoiTop(1, 3, N);

console.log(cnt + '\n' +answer.join('\n'));