# \[99클럽 코테 스터디 7일차 TIL]  프로그래머스 - 하노이의 탑

## \[level 2] 하노이의 탑 - 12946

[문제 링크](https://school.programmers.co.kr/learn/courses/30/lessons/12946)

#### 문제 설명

하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.

1. 한 번에 하나의 원판만 옮길 수 있습니다.
2. 큰 원판이 작은 원판 위에 있어서는 안됩니다.

하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.

1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.

**제한사항**

* n은 15이하의 자연수 입니다.

***

**입출력 예**

| n | result                      |
| - | --------------------------- |
| 2 | \[ \[1,2], \[1,3], \[2,3] ] |

**입출력 예 설명**

입출력 예 #1\
다음과 같이 옮길 수 있습니다.

![Imgur](https://i.imgur.com/SWEqD08.png)\
![Imgur](https://i.imgur.com/mrmOzV2.png)\
![Imgur](https://i.imgur.com/Ent83gA.png)\
![Imgur](https://i.imgur.com/osJFfhF.png)

***

## 풀이 코드

```java
import java.util.*;

class Solution {
    
    private List<int[]> arr = new ArrayList<>();
    
    public int[][] solution(int n) {
        int[][] answer = {};
        hanoi(n, 1, 2, 3);
        answer = arr.toArray(new int[0][]);
        return answer;
    }
    
    private void hanoi(int n, int start, int mid, int to) {
        if (n == 1) {
            arr.add(new int[]{start, to});
            return;
        }
        hanoi(n - 1, start, to, mid);
        arr.add(new int[]{start, to});
        hanoi(n - 1, mid, start, to);
    }
}
```

* Time: 3.05 ms
* Memory: 94.8 MB

위 코드의 하노이 함수를 통해 구할 수 있다.

***

## 돌아보기

해당 문제는 풀지 못했다. 어느정도 규칙은 있는 것 같았는데 그 규칙을 구현하는 방법을 도저히 모르겠어서 검색을 통해 알게 됐다. 근데 정답 풀이를 봐도 왜 풀리는지는 여전히 이해하지 못하겠다.

재귀 함수를 활용하는 능력이 많이 부족함을 깨닫는다.

### 다음에는

1. 재귀 함수 문제들을 풀어보면서 감 잡기
2. 이해할 때까지 포기하지 않기

***

\#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://devlee.gitbook.io/docs/study/99/99-7-til.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.