[JavaScript/재귀] 백준 골드 5 : 11729 - 하노이 탑 이동 순서

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

---

📌 작성한 코드 

// 11729
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim();
const k = Number(input);
const route = [];

const hanoi = (start, end, n) => {
    if (n === 1) {
        route.push(`${start} ${end}`);
        return;
    }

    hanoi(start, 6 - start - end, n - 1);
    route.push(`${start} ${end}`);
    hanoi(6 - start - end, end, n - 1);
};

hanoi(1, 3, k);
console.log(2 ** k - 1);
console.log(route.join("\n"));

 

📌 설명 

하노이의 탑을 푸는데 참고한 글은 '바킹독 님의 실전 알고리즘 - 재귀'이다. 요새 바킹독님의 글을 보며 알고리즘을 공부하고 있다.

https://blog.encrypted.gg/943

 

하노이의 탑의 문제를 보면 큰 숫자 위에 작은 숫자의 칸만 올 수 있고, 한번에 맨 위의 블럭 한개만 이동할 수 있다. 이 점을 주의하면서 문제를 풀어보자. n번째 블럭을 3번으로 이동하기 위해서는 작은 블럭 위에 큰 블럭이 올라갈 수 없고, 맨 위의 블럭만 이동할 수 있으므로 n-1개의 블럭을 2번으로 이동시켜야 한다. 그리고 나서 n을 3번으로 이동 시킨다. 그 다음에는 이제 n-1 블럭을 3으로 이동 시킬 것이다. 이전 방법과 마찬가지로 n-1을 옮기기 위해서는 n-2개의 블럭을 1번으로 이동시켜야 한다. 그리고 나서 n-1블럭을 3번으로 이동 시킨다. 

 

이렇게 단계를 보니까 어떻게 해야할지 감이 온다. 이런 방식으로 코드를 짜면 될 것이다.

1. n-1 블럭을 출발과 도착 지점이 아닌 곳으로 이동시킨다.

2. n 블럭을 도착 지점으로 이동시킨다.

3. n-1 ~ 1 동안 1,2 단계를 반복한다.

 

여기서 생각해야 할것은 n의 이동을 위해 n-1 블럭을 이동 시켜야 하는데 어디로 이동 시켜야 할까?이다. 현재 이동시키고자 하는 이유가 도착 지점에 n을 가져다 놓기 위해 위의 블럭을 치우는 것이므로 도착 지점이 아닌 곳으로 이동 시켜야 한다. (6-start-end : 세 위치의 합이 6이기 때문)

// 의사 코드 
1. 움직이고자 하는 블럭 위에 있는 블럭들을 전부 도착 지점이 아닌 곳에 이동시킨다.
2. 블럭을 도착 지점에 움직인다
3. 다음 블럭을 도착 지점으로 이동시킨다 (1->2 반복)

hanoi(start, 6 - start - end, n - 1); // 1. n-1개의 블럭을 도착 지점 아닌 곳으로 이동
route.push(`${start} ${end}`); // 2. n 이동
hanoi(6 - start - end, end, n - 1); // 3. 이제 n-1을 도착지점으로 이동

 

재귀로 구현하였기 때문에 이는 이렇게 동작하게 된다.

n-1를 2로 치우기 -> n-2를 3으로 치우기 ->  .... -> 1을 (2 or 3)으로 치우기. 그러므로 우리는 n=1일 경우 이동 없이 바로 이동 시킬 수 있는 조건을 넣어주면 해당 재귀 함수는 재귀가 종료되는 조건이 갖춰지므로 우리가 원하는 대로 동작하게 될 것이다. 이렇게 해서 우리는 n개의 블럭이 있을 때 하노이 탑의 이동 기록을 출력하는 `hanoi` 함수를 작성할 수 있다.

const hanoi = (start, end, n) => {
    if (n === 1) {
        route.push(`${start} ${end}`);
        return;
    }

    hanoi(start, 6 - start - end, n - 1);
    route.push(`${start} ${end}`);
    hanoi(6 - start - end, end, n - 1);
};

 

✅성공