[JS] 백준 11792 : 하노이 탑 이동 순서 - 재귀

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

11729번: 하노이 탑 이동 순서

 

풀이방법

1. 세 개의 장대 -> 시작 장대, 나머지 장대, 목적지 장대라는 기준을 둔다.

2.  두 번의 수행과정을 거쳐야함 

 - 1. 첫번째로 맨 밑의 원반을 제외한 원반들은 모두 나머지 장대에 옮겨져야한다.

    -그래야 맨 밑의 원반이 목적지 장대로 갈 수 있다.

    -원반의 개수가 몇개던 간에, 시작 장대(start)에서 목표기둥(final)으로 모든 원반을 옮기기 위해서

맨 밑의 원반이 목표 기둥으로 옮겨져야 하는 것은 필수 과정이다.

 - 2. 두번쨰로 맨 밑의 원반이 목적지 장대에 도달 했다면 나머지 장대에 있던 원반들이 목적지 장대로 옮겨져야한다.

3. 이때 1번 과정인 맨 밑의 원반을 제외한 원반들은 모두 나머지 장대에 옮겨져야한다. 를 수행하기 위해서는 재귀적으로 수행해야한다.

 - 입력된  N개의 원반을 한개 씩 줄여가면서 그 원반을 목적지 장대가 아닌 나머지 장대에 재귀적으로 이동시킨다.

 - 즉 원반이 2개 이상일 때 부터는 나머지 장대에 맨 밑 원반을 제외한 모든 원반을 옮겨야 한다.

 

 

---

 

 

한번 N=3일때를 재귀적으로 이동해보자

 

1. n=1이 되었을 때 

 -원판 하나가 1에서 3으로 가게된다.

2. 위의 함수가 종료됨에 따라서 hanoi(2,1,3,2)로 돌아와서 원판을 또 옮겨준다.

 -원판 하나가 1에서 2로 이동한다.

 -이후 다른 곳에 옮겨놓았던 원반을 현재 위에 올림

3. 그러면 재귀적으로 수행했던 함수들이 모두 종료되고 다시 처음으로 돌아온다.

 -이제 1번에 있는 원판을 3번으로 옮긴다. hanoi(3,1,2,3) => 1번에 있는 원판을 3번으로 이동하는데 2번을 보조로 사용이라는 뜻 -> 즉 이전의 수행했던 것이 아래의 결과물을 나오게 한 것임

 

4. 이제 다시 2번에 있는 원판 한 개를 1번으로 옮김

- 우리가 수행하려고 했던 과정 중 하나인 맨 밑 원판을 목적지로 옮겼으니 나머지장대에 있는 원판에서도 다시 맨 밑 원판을 목적지 장대로 옮겨야 한다.

5. 나머지 장대에있던 원판을 목적지 장대로 옮긴다.

7. 그리고 마지막으로 하나남은 원판을 목적지로 옮긴다.

 

 

---

재귀적으로 수행된다는 것을 이해하기위해 검색하던 도중 아래와 같이 트리로 정리한 이미지를 발견했다.

트리로 펼쳐놓음으로 더 이해가 쉬울 수 있을 것 같다는 생각에 저장했다.

 

 

내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input = input.replace(/\r/g, "").split("\n");

const N = Number(input.shift());

let count = 0;
let answer = [];

// hanoi(원반개수-1, 시작, 나머지 , 목적지) => 맨 밑 원반을 제외한 모든 원반을 나머지기둥으로 옮긴다
function Hanoi(num, from, other, to) {
  if (num === 1) {
    answer.push([from, to]);
    count++;
    return;
  } else {
    Hanoi(num - 1, from, to, other);
    answer.push([from, to]);
    count++;
    Hanoi(num - 1, other, from, to);
  }
}
Hanoi(N, "1", "2", "3");
console.log(count);
console.log(answer.map((element) => element.join(" ")).join("\n"));

 

 

 

 

이 문제를 쉽게 이해하려면 

function Hanoi(num, 시작, 나머지, 목적지) {
  if (num === 1) {
    answer.push([from, to]);
    count++;
    return;
  }
 }

이 함수를 잘 이해하면 된다.

여기에 num=2일 때를 이용해보자

일단 위 함수의 뜻은

"원 판이 1개라면 시작기둥에 원판을 목적지로 옮기고  함수를 종료하라"

라는 뜻이다.

---

원판이 하나일 때는 목적지로 바로 가겠지만

두 개 이상일 때는 원판이 나머지 기둥 또는 목적지 기둥으로 갈 수 있다.

 

하지만 목적지 기둥에는 가장 큰 원판인 맨 밑 원판이 가야한다.

그래서 맨 밑 원판을 제외한 모든 원판은 나머지 기둥으로 가야한다. -> 이것이 목표

 

 

다시 돌아와서 함수를 수행하면서 num=1이 아니라면 재귀적으로 다시 함수를 호출하는데 -> 위 목표를 함수로 표현

나머지 기둥을 보조로 사용하기 위해 

hanoi(num - 1, 시작, 목적지, 나머지);

라는 함수를 호출하게 된다. (현재 num은 1)

 

이 함수는

"맨 밑의 원반을 제외한 모든 원판을 나머지 기둥으로 옮겨라"

이라는 뜻이다.

 

---

위 함수에 따라 맨 밑의 원반을 제외한 모든 원판을 나머지 기둥으로 옮겼다면

시작기둥에 있던 원판을 목적지 기둥으로 옮긴다.

이를 코드로 표현하면 아래와 같다.

answer.push([from, to]);
count++;

이 코드가 중간에 추가되어있는 이유이다.

---

 

이후에 목적지로 간 원판이 이동하거나 그 위에 원판을 못 옮기는 경우가 생길까??

 

답은 "그러한 경우는 생기지 않는다" 이다.

 

당연히 가장 큰 원판이 목적지로 갔기 때문이다.

 

그러므로 이 후 부터는 원래의 원판 갯수에서 1개를 뺀 수로 풀이를 진행한다.

 

 

 

이제 처음과 달라진 부분이 생기게 된다.

우선 원반의 갯수를 한개 를 뺀 상태이고, 나머지 기둥에 나머지 원판들이 있는 상태이다.

 

그럼 다음 풀이를 진행 할 때에는

원래 나머지 기둥이였던 기둥을 시작기둥으로 

원래 시작 기둥이였던 기둥을 나머지 기둥으로 변경해서 진행해야한다.

hanoi(num - 1, 나머지, 시작, 목적지);

 

이를 반복하게되면 N개의 원판을 모두 옮길 수 있게 된다.

 

 

 

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