https://programmers.co.kr/learn/courses/30/lessons/12946
하노이의 탑
문제 설명
하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.
한 번에 하나의 원판만 옮길 수 있습니다.
큰 원판이 작은 원판 위에 있어서는 안됩니다.
하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.
1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.
제한사항
n은 15이하의 자연수 입니다.
입출력 예
| n | result |
|---|---|
| 2 | [ [1,2], [1,3], [2,3] ] |
이문제를 풀기 전 하노이의 탑이 어떻게 움직이는지부터 찾아봤다.
그리고 다시 문제를 확인해보니 어떻게 풀어야할지 솔직히 감이 오지 않았고 다른 사람의 풀이를 확인했다.
function solution(n) {
var answer = [];
const hanoi = (n,s,m,e) => {
if(n === 1) {
answer.push([s,e])
return;
}
hanoi(n-1,s,e,m);
answer.push([s,e]);
hanoi(n-1,m,s,e);
}
hanoi(n,1,2,3)
return answer;
}솔직히 답을 봐도 어떻게 행동하게 될지 이해가 되지 않아서 debugger를 따라가면서 문제를 확인했다.
먼저 n이 4일경우를 생각했고
n이 1이 될때까지 재귀가 이어진다.(e와m이 계속 바뀐다. 홀수인 하노이의탑과 짝수인 하노이의 탑 시작 행동이 다르기 때문이라고 생각한다.)
n이 1이 됐을 때 s는 1 e는 2인 상태로 먼저 가장작은판(이하 A)을 2번칸에 놓게 된다.
그렇게 되면서 n이 1일 때 재귀가 끝나면서 n이 2인 재귀가 진행된다.
answer.push([s,e])
이 경우 s는 1 e는 3 m 은 2가 되면서 [1,3]이 정답에 추가가 된다. 두번째로 작은판(이하 B)는 3번째 칸으로 이동하게 된다.
그 다음으로 다시 재귀가 진행되는데 hanoi(1,2,1,3) 이 진행되게 되면서 정답에 [2,3]이 추가로 들어오게 된다. A가 B 위로 올라간다.
이상태로 n이 2인 재귀가 끝나게 되고 n이 3인 재귀 hanoi(3,1,2,3)이 진행된다.
정답에 [1,2]를 넣어주고 판C가 2번째 칸에 놓아진다.
그리고 hanoi(2,3,1,2) 재귀함수가 다시 시작된다.
[3,1] 이 추가되면서 A가 1번칸으로 이동하고 [3,2] B가 2번칸으로 이동한다. 그리고 A가 다시 2번칸으로 이동한다.([1,2])
이렇게 n이 3일때의 재귀가 끝이나고 n이 4일때 를 다시 반복하게 된다.
재귀를 따라가다보니 출발 경유 도착에 대해 이해가 가기 시작했다.
먼저 짝수일 때는 경유가 2번 홀수일 때는 경유가 3번으로 계속 2번과 3번을 반복하면서 진행됐다.
재귀에 대해서 아직 많은 점이 부족하고 어렵다. 조금 더 이해할 수 있도록 꾸준히 공부를 해야겠다.
