문제 출처 : https://school.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 | result |
|---|---|
| 1 | [ [1,2], [1,3], [2,3] ] |
제한사항
- n은 15이하의 자연수 입니다.
접근
큰 원판은 작은 원판보다 반드시 아래에 있어야 한다는 조건 때문에 작은 원판들은 출발지start에서 목적지end로 향할 때 반드시 경유지mid가 있어야 한다.
문제풀이
function solution(n) {
const answer = []; // 새배열
function move(n, start, end, mid) {
//n은 옮길 원반의 수,
//start는 원반들이 있는 기둥,
//end는 원반을 옮길 끝 기둥,
//mid는 중간 기둥
//Base case
if (n === 1) {
answer.push([start, end]);
}
//Recursion case
else {
move(n - 1, start, mid, end);
answer.push([start, end]);
move(n - 1, mid, end, start);
}
}
move(n, 1, 3, 2); // 1번 기둥-> 3번 기둥으로 n개의 원반을 "2번 기둥을 경유하여" 옮긴다.
return answer; //최소 이동 횟수로 원반을 옮기는 순서를 배열`answer`에 저장하고 return
}
Base case
(더 작은 부분 문제로 나눌 수 없는 상태)
옮겨야 할 원반의 수
n이 1일 때,
하나의 원반만 남았을 때, 그 원반을 시작 기둥에서 끝 기둥으로 직접 옮기고, 새 배열에 추가
Recursion case
(문제를 더 작은 부분 문제로 나누어 계속해서 재귀 호출)
원반의 수가 1보다 클 때 , 세가지 단계로 나누어 접근.
-
상위
n-1개의 원반을시작 기둥에서중간 기둥으로 옮긴다. (start -> mid) 1 2 -
가장 큰 원반 (
n번째 원반)을시작 기둥에서끝 기둥으로 직접 옮긴다. (start -> end) 1 3 -
중간 기둥에 있는n-1개의 원반을끝 기둥으로 옮긴다. (mid -> end) 2 1
재귀적으로
move함수를 호출하면서 각 단계의 원반 이동을 수행.
- 첫 번째
move호출,n-1개의 원반을중간 기둥으로 옮긴다 , 여기서 end는 중간 기둥으로 사용.
큰 원반을 제외한 "모든 원반을 중간 기둥"으로 옮겨서, 가장 큰 원반을 올릴 수 있는 공간을 만드는 것.
-
남은 가장 큰 원반을 직접
끝 기둥으로 직접 옮긴다. , 끝 기둥에 다른 원반들이 없으므로 바로 옮길 수 있다. -
두 번째
move호출,중간 기둥의 원반들을 최종 목적지인끝 기둥으로 옮긴다. , 여기서 start는 중간 기둥으로 사용.
다른사람의 풀이
function solution(n) {
const answer = [];
const hanoi = (n, from, to, by) => {
if (n === 1) {
answer.push([from, to]);
return;
}
hanoi(n - 1, from, by, to);
answer.push([from, to]);
hanoi(n - 1, by, to, from);
};
hanoi(n, 1, 3, 2);
return answer;
}