하노이탑 이동 순서(백준 코딩테스트 1992번, DFS, NodeJS 풀이)

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

 

 

문제 수준:

실버1, DFS

 

문제 요약:

유명한 하노이탑 문제이다. 

1번 영역에서 3번 영역으로 모든 탑을 옮기면 되는 문제이다. 조건은 2가지 있다.

1. 한 번에 1개의 디스크만 옮길 수 있다.

2. 자신보다 작은 디스크 위에 더 큰 디스크를 올려놓을 수 없다.

 

이때 탑의 높이가 주어지면 최소 몇 번의 이동으로 3번까지 옮길 수 있는지를 구하여라.

 

 

 

입출력 예 (입력 / 출력):

 

 

문제 풀이 전략:

결국 가장 아래에 깔린 가장 큰 디스크가 3번 영역에 도달을 해야 나머지를 옮길 수 있다.

 

그 말인 즉슨 N개의 디스크가 있다면 N-1개의 디스크를 2번 영역(보조영역, Auxiliary)에 옮겨놔야(step1 -> step2)

1번의 맨마지막 디스크를 3번으로 옮길 수 있다. (step2 -> step3)

그리고 N-1개의 디스크를 목적지까지 옮기면 끝이다.

 

절차적으로 사고해서 너무 어렵게 생각하면 안된다.

n-1개를 2번 영역으로 옮기기에 집중하면 된다.

그렇게 하다 보면 (n-1번을 2번 영역으로 옮기려면 n-3개를 3번 영역에 일단 둬야하고... )

재귀적인 반복이 눈에 띄게 된다.

 

 

내 풀이:

let fs = require("fs");
let N = +fs.readFileSync("./dev/stdin").toString().trim().split("\n"); //숫자 입력값

const answer = [];
let cnt = 0;

function hanoiTower(num, from, middle, to) { //재귀함수에 총 디스크 갯수, 출발지, 중간지, 목적지를 인자로 설정
  if (num === 0) { // 디스크가 해당 영역에 아무것도 없으면 반환 기저조건 발생
    return;
  } else { // 해당 영역에 디스크가 있다면
    hanoiTower(num - 1, from, to, middle); //n-1개를 목적지에서 중간으로 이동시키는 재귀 실행(재귀를 할때 마다 middle과 to가 계속 번갈아 실행된다.)
    answer.push(from + " " + to); // 출발지에서 목적지로 옮기기 (맨 마지막 디스크도 옮겨짐)
    cnt++; // 옮기고 나서 카운터 1 올리기.
    hanoiTower(num - 1, middle, from, to); (디스크 n-1개를 middle을 출발지로해서 to로 옮기기)
  }
}

hanoiTower(N, "1", "2", "3"); // 재귀 실행
console.log(cnt); // 카운터 표출
console.log(answer.join("\n")); //답 표출

 

솔직히 어떻게 이게 dfs 기본 문제인지 모르겠다. 매우 유명한 문제여서 푸는 방식을 다들 기억하니까 푸는거지

2개의 재귀함수가 엃히면서 1->3, 1->2, 3->2 이런식으로 계속 weaving되는 것을 처음엔 예측하기가 힘들다.

 

...라고 예전엔 생각했는데, 지금 생각했을 때는 대단한 조작을 절차적으로 해줄 생각을 하면 복잡해진다는걸 명심해야된다.

점화식을 짜는 사고를 해야된다. 각 단계에서 재귀함수는 그 단계의 목표에만 집중하면 된다.