하노이 타워 2

문제 설명

크기가 1부터 n까지인 서로 다른 n개의 원판과 세 개의 기둥이 있는 하노이 타워가 있습니다. 모든 원판은 크기가 큰 것이 아래로 오도록 순서대로 쌓여 1번 기둥에 놓여 있으며, 다음과 같은 이동 규칙을 따릅니다.

1. 한 번에 하나의 원판만 옮길 수 있습니다.
2. 각 기둥의 맨 위에 있는 원판만 이동할 수 있습니다.
3. 작은 원판 위에 큰 원판을 올려놓을 수 없습니다.

이때 1번 기둥에 있는 모든 원판을 3번 기둥으로 최소 횟수로 옮기려고 합니다.
모든 이동 과정은 [원판의 크기, 출발 기둥 번호, 도착 기둥 번호] 형태로 순서대로 기록되어야 합니다.

자연수 n이 주어질 때, 위의 이동 규칙을 따라 모든 원판을 옮기는 과정을 실제 수행 순서대로 기록한 이차원 정수 배열을 반환하는 solution 함수를 작성하시오.

제한 사항

• n은 1 이상 20 이하의 자연수입니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 1개의 원판을 1번 기둥에서 3번 기둥으로 옮기는 경우, 크기 1의 원판을 1번 기둥에서 3번 기둥으로 이동하는 [1, 1, 3] 과정이 기록됩니다.

2번 테스트케이스 설명

• 2개의 원판을 1번 기둥에서 3번 기둥으로 옮기는 경우, 크기 1과 2의 원판이 아래 순서대로 이동하는 과정이 기록됩니다:

  • 크기 1 원판 : 1 → 2

  • 크기 2 원판 : 1 → 3

  • 크기 1 원판 : 2 → 3

3번 테스트케이스 설명

• 3개의 원판을 1번 기둥에서 3번 기둥으로 옮기는 경우, 크기 1부터 3까지의 원판이 아래 순서대로 이동하는 과정이 기록됩니다:

  • 크기 1 원판 : 1 → 3

  • 크기 2 원판 : 1 → 2

  • 크기 1 원판 : 3 → 2

  • 크기 3 원판 : 1 → 3

  • 크기 1 원판 : 2 → 1

  • 크기 2 원판 : 2 → 3

  • 크기 1 원판 : 1 → 3