https://www.acmicpc.net/problem/11729
11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
- 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
- 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다.

2. 입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.
3. 출력
첫째 줄에 옮긴 횟수 K를 출력한다.
두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

3.1. 내가 제출한 코드
let fs = require('fs');
let input = fs.readFileSync("/dev/stdin").toString();
let N = Number(input);
let count = 0;
let answer = [];
function Hanoi(num, from, other, to){
if(num === 0) {
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"));
3.2. 풀이
이 문제를 이해하는데 굉장한 시간을 쏟아야만 했다. 그냥 머리속으로 이렇게 옮기고 저렇게 옮기는 것은 쉬웠지만
function 속에서 콘솔하는 순서가 어떻게 되는지 도무지 이해가 되지 않았기 때문이다.
이 문제를 풀기 위해선 재귀함수와 이진트리 순회라는 것을 이해하고 있어야 했다.
전위, 중위, 후위순회가 있고, 이 코드에서 쓰이는건 중위순회이다.

이진트리 순회를 그림으로 보는건 이해가 잘 됐지만 또 코드에 대입하려니 골머리가 ...
아무튼 맨 처음 들어가는 값을 (3, 1, 2, 3)로 정하고 처음의 뿌리로 정한다.
순서대로 (3 = Num) (1 = 초기값) (2 = 옮겨진 값과 다른 한 곳) (3 = 옮겨질 값)
내가 이해한게 맞다면 일단 계산을 아래처럼 미리 다 해놓고 맨 밑 왼쪽부터 시작해서
(왼쪽 뿌리 오른쪽)(왼쪽 한 뭉텅이) - 뿌리 - (오른쪽 한 뭉텅이)(왼쪽 뿌리 오른쪽) 요런식으로 써 나가면 된다.
(3, 1, 2, 3)
/ \
(2, 1, 3, 2) (2, 2, 1, 3)
/ \ / \
(1, 1, 2, 3) (1, 3, 1, 2) (1, 2, 3, 1) (1, 1, 2, 3)
'백준 문제' 카테고리의 다른 글
[백준] 1927 최소 힙 JavaScript (1) | 2024.06.18 |
---|