어려움재귀

하노이 탑

기둥이 세 개(1번, 2번, 3번) 있고, 1번 기둥에 크기가 다른 원판 n개가 큰 것이 아래로 가도록 쌓여 있어요. 이 원판을 모두 3번 기둥으로 옮기려고 해요.

규칙은 두 가지예요. 한 번에 맨 위 원판 하나만 옮길 수 있고, 큰 원판을 작은 원판 위에 올릴 수 없어요.

최소 횟수로 옮기는 이동 순서를 반환해요. 각 이동은 [출발 기둥, 도착 기둥]이고, 이동들을 순서대로 담은 배열을 돌려줘요.

핵심 아이디어는 이래요. n개를 옮기려면, 먼저 위 n-1개를 2번(여분 기둥)으로 옮기고, 가장 큰 원판을 3번으로 옮긴 뒤, 2번의 n-1개를 다시 3번으로 옮기면 돼요. 이 자체가 재귀예요.

예시

예시 1

입력: n = 1
출력: [[1, 3]]
설명: 원판 하나를 1번에서 3번으로 옮기면 끝이에요.

예시 2

입력: n = 2
출력: [[1, 2], [1, 3], [2, 3]]
설명: 작은 원판을 2번으로, 큰 원판을 3번으로, 작은 원판을 3번으로 옮겨요.

제한 사항

1 ≤ n ≤ 12
이동 횟수는 항상 2^n - 1 번이에요.

go(k, from, to, via)를 만들어요. k가 0이면 아무것도 안 해요. 아니면 go(k-1, from, via, to)로 위 원판들을 여분 기둥에 옮기고, [from, to]를 기록한 뒤, go(k-1, via, to, from)로 여분 기둥의 원판들을 목적지로 옮겨요.

javascript
Copy code
function hanoi(n) {
  const moves = [];
  function go(k, from, to, via) {
    if (k === 0) return;
    go(k - 1, from, via, to);
    moves.push([from, to]);
    go(k - 1, via, to, from);
  }
  go(n, 1, 3, 2);
  return moves;
}

이전 문제병합 정렬 직접 구현

다음 문제트리의 최대 깊이

예시 테스트만 실행 (Cmd/Ctrl+Enter)

숨김 테스트까지 채점 (Cmd/Ctrl+Shift+Enter)

에디터를 불러오고 있어요…

코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.