[백준, 11729번] 하노이 탑 이동 순서 (재귀 , Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 하노이 탑 이동 순서" 문제는 하노이탑 알고리즘을 사용하는 대표적인 문제입니다. 다음과 같은 제약사항이 있는 상황에서 목적지 까지 옮기는 횟수와 순서를 출력하는 문제입니다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

---

하노이 탑 전체 이동 순서

 

위와 같이 첫 번째 기둥에서 마지막 기둥까지의 이동순서가 나오며, 하노이 탑(Hanoi Tower) 알고리즘의 최소 이동 횟수는 다음 공식으로 계산됩니다.

2^n - 1

 

이 때 공식을 알고있으면 최소 이동 횟수는 간단하게 구할 수 있지만, 문제의 핵심은 이동 순서를 출력해야한다는 것 입니다.

---

문제의 목표는 모든 원판을 첫 번째 장대에서 세 번째 장대로 옮기는 것입니다. 이때 주어진 제약 조건을 지켜야 합니다.

 

가장 큰 원판을 목적지로 옮기기 위해서는, 먼저 그 위에 있는 모든 원판들을 임시 기둥으로 이동시켜야 합니다.

 

그 다음 가장 큰 원판을 목적지 기둥으로 옮기고, 마지막으로 임시 기둥에 있는 원판들을 크기 순서에 맞게 목적지 기둥으로 이동시키면 됩니다.

 

정리하자면,

 

💡 기본 원리 (재귀) 

1. 가장 작은 원판(1)부터 이동
2. 작은 원판들이 이동할 공간(tmp 기둥)을 확보
3. 큰 원판을 목표 기둥(end)으로 이동
4. 임시로 옮겨둔 작은 원판들을 다시 목표 기둥으로 이동

---

전체 코드

 

재귀 함수의 마지막 매개변수 count는 현재 이동해야 할 원판의 개수를 나타냅니다. 실제 원판의 이동 과정은 StringBuilder를 사용하여 기록하고 출력합니다.