[JavaSrcipt] Baekjoon - 11729 : 하노이 탑 이동 순서

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

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

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

 

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

 

예제입력	예제출력
3	7 1 3 1 2 3 2 1 3 2 1 2 3 1 3

⭕ 풀이

const input=require('fs').readFileSync('/dev/stdin').toString().trim();
let n=Number(input);
let answer=[];
let count=0;

function hanoi(num,start,to,sub){
    
    if(num==1){
        
        answer.push([start,to]);
        count++;
        return;
        
    }else{
        
        hanoi(num-1,start,sub,to);
        answer.push([start,to]);
        count++;
        hanoi(num-1,sub,to,start);
        
    }
}

hanoi(n,'1','3','2');
console.log(count)
console.log(answer.map((x)=>x.join(' ')).join('\n'));

 

하 이거 다른분들 풀이코드를 보고 직접 적어가며 했는데도 왜 이렇게 나오지?하는부분이

한두군데가 아니었다..

포기하려다가 지금 모른척해도 나중에 다시 배워야할게 뻔하므로 이해해보도록한다.

 

우선 3으로 예를들면

기반조건이 num==1이므로

num-1함수를 재귀호출하며

num==1을 만족할경우 해당 실행문을 실행한뒤 return이다

이때 num-1을 해서 num==1이 된것이므로

return을 하면 이전단계인 num이 2였던상태가된다.

 

여기까지오면 

else의 num이 2인상태에서의 첫hanoi가 끝난것이다.

이제 num이 2인상태에서 answer.push를 하고

두번째 hanoi로 넘어간다.

마찬가지로 num-1을하여 num==1이될때까지 실행.

 

기반조건인 num==1을 만족해 return을 했다면 이제

num이 2였던상태에서의 두번째hanoi까지 다 끝났다.

즉, num이 3이었던 상태에서의 첫번째hanoi가 끝난것이다.

 

이제 num이 3인상태에서의 answer.push를 하고

이제 num이 3인상태에서의 두번째hanoi로 가자.

 

num-1과 갖고있는 해당인자들을 순서에 맞게

즉 num에 2를 넣고 재귀호출하며

 

다시 기반조건인 num==1을 만족할경우 실행문 실행 뒤return

즉 다시 이전단계인 num이 2인상태로 올라왔다.

else의 num이 2인상태에서의 첫hanoi가 끝난것이다.

이제 num이 2인상태에서 answer.push를 하고

두번째 hanoi로 넘어간다.

마찬가지로 num-1을하여 num==1이될때까지 실행.

 

num==1을 만족해 return을 했다면 이제

num3 인상태에서의 두번째 hanoi까지 다 끝난것이다.

 

나름 풀어본다고 내가 직관적으로 이해한대로 써봤는데 더 복잡해지는 기분이다.

 

즉

입력값을 3을 받았으면

재귀호출이 2개이므로 2를 넣고 2개를 실행하며

또 재귀호출이 2개이므로 2를넣고 2개를 실행하면 1을넣고 4개를 실행하게 된다고 보면될것같다.

3일때 1번 2일때 2번 1일때 4번 총 7번을 움직여야한다.

 

다른코드를 봐도 작동순서가 어떻게되는지 return이면 어디까지 돌아가야하는건지 모르니

손으로 풀던 메모장에쓰던 답이 나오지않던것이다..

 

출처를 달아둔 유튜버분의 영상에서 해당코드를 실행하면 어느부분이 어떻게 실행되는지 

친절하게 그림으로 설명해주셔서 다행히 이해가 됐다!

 

아래에는 이해한뒤 직접 이게 맞는가 풀어본것이다.

★3132

num 3
start 1
to 3
sub 2

num==1 아님

else
num start sub to
2     1     2    3를 호출하면
num start to sub로 받음
2     1     2    3

★★2123

num 2
start 1
to 2
sub  3

num==1아님
else
num start sub to
1      1     3    2를 호출하면
num start to sub로 받음
1      1     3    2

★★★1132

num 1
start 1
to 3
sub 2

num1 맞음
start,to push    ●1,3 count
-return

★★2123
push.start,to  ●1,2 count

count++아래재귀호출
현재
num 2
start 1
to 2
sub  3인상태

num-1 sub to start
1         3   2    1

★★★1321
num 1
start 3
to 2
sub 1

num==1맞음
start,to push   ●3,2 count
-return

★★2123 끝

★3132
start,to push  ●1,3 count

num 3
start 1
to 3
sub 2

num-1 sub to start 호출
2        2    3    1

★★2231

num 2 
start 2
to 3
sub 1

else 

num-1 start sub to 호출
1        2     1     3

★★★1213

num==1맞음
push start,to    ●2 1 count
-return

★★2231
push start to  ●2 3     count

num 2
start 2
to 3
sub 1

num-1 sub to start 호출
1         1   3   2을넣어서
num start to sub로 받으니 start to= 1 3

★★★1132

num==1 맞음
push start to ●1 3 count
-return

 

 

 

 

 

 

-출처

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

 

-이해돕기

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