백준 11729번

하노이의 탑 문제 일단 코드부터 보자면 

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(__dirname + '/input.txt').toString().split('\n')

let cnt = 0;
let ans = ''
function hanoi(N,start,goal,sup) { // (원판개수,시작,목표,보조)
    if(N===1) { // 원판개수가 1개면 그냥 바로 목표 기둥으로 옮기면 끝이기 때문에 이렇게 적어줌 
// N이 0일때라고 해주고 그냥 return만 써주어도 된다.
        ans += `${start} ${goal}`+ '\n'
        cnt++
        return;
    }
    hanoi(N-1,start,sup,goal); // 하노이 탑의 핵심부분 가장 큰 원판을 제외한 나머지 원판은 일단 보조기둥으로 옮겨놓아야 한다 그러니까 원판이 N개 라면 
// N-1개 원판을 보조기둥으로 옮겨야 된다는 의미 그과정을 코드로 표현한 부분 
    ans += `${start} ${goal}`+ '\n' // 다 옮겼다면 시작기둥에 있는 가장 큰 원판을 목표기둥으로 옮긴다
    cnt++;
    hanoi(N-1,sup,goal,start);// 그리고 보조기둥에 있는 N-1개 원판을 목표기둥으로 옮겨야 한다 
}

hanoi(+input[0],1,3,2)
console.log(cnt); // 원판을 옮기는 회소 이동 횟수 공식이 있는데 2^N(원판갯수)-1 이렇게 해줘도 된다. 
console.log(ans);

하노이의 탑이 뭐냐면 세개의 장대가 있고 첫번째 장대에 원판을 세번째 장대로 옮기는 것인데 규칙이 있음 

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 조건을 가지고 원판을 옮긴 횟수와 옮긴 과정을 출력을 해주는 문제 

 

일단 종료조건은 원반의 개수가 하나일때 일것이다. 한개면 그냥 시작 기둥에서 목표기둥으로 바로 옮기면 끝이기 때문에 

그다음 원판이 1개 이상일때 시작기둥에서 목표기둥으로 옮기려면 보조기둥을 거쳐가야하는데 

1. 가장 큰 원판을 제외한 나머지 N-1개 원판이 보조기둥에 일단 옮겨져 있어야 하고 
2. 가장 큰 원판을 목표 기둥에 옮기면 
3. 보조 기둥에 있던 나머지 원판을 목표 기둥으로 옮긴다 

그리고 옮긴 최소 횟수 구하는 거에 

console.log(Math.pow(2,+input[0])-1);

이렇게 해줘도 됨 왜냐면 옮긴 최소 횟수 구하는 공식이 2^N(원반개수)-1 이기 때문이다.

 

여기까지는 어찌저찌 이해가 간다 근데 함수 부분이 좀 이해가 안가서 정리하자면 

hanoi(N,start,goal,sup) -> N개의 원판을 시작기둥(start)에서 목표기둥(goal)까지 보조기둥(sup)를 이용해서 옮겨라

 

hanoi(N-1,start,sup,goal) -> N-1개의 원판을 시작기둥(start)에서 보조기둥(sup)까지 목표기둥(goal)를 이용해서 옮겨라

hanoi(N-1,sup,goal,start) ->  N-1개의 원판을 보조기둥(sup)에서 목표기둥(goal)까지 옮겨라 

 

대강 이정도 의미구나만 알고 있으면 될것 같다. 왜냐면 재귀함수는 하나하나 그 작동원리를 파해쳐 나갈려고 하면 오히려 이해하는데 더 방해가 되기 때문이다.