하노이의 탑

링크텍스트

문제 설명

하노이탑

1. 3개의 기둥이 있다.

2. 첫 번째 기둥에 크기가 작은 원판이 위로 올라가있는 n개의 원판이 있다.

3. 이 원판들을 마지막 기둥으로 옮긴다.
   3-1. 이때, 크기가 작은 원판은 크기가 큰 원판 아래에 있을 수 없다.
   3-2. 한번에 하나의 원판만 움직일 수 있다.

문제 풀이

사실 n번째 푸는 문제여서 원리를 외워서 풀었음.

정답 풀이

1. 재귀함수를 이용하여 푼다. 이때 재귀함수는 move(남은 원판 갯수, 시작, 중간, 도착)으로 구성한다.

2. 시작: move(n,1,2,3) -> n개의 원판을 2(중간)를 거쳐 1에서 3으로 옮긴다.

3. 재귀
   3-1. 종료 조건: n==0이면 더 이상 옮길 원판이 없다는 것이므로 return 한다.
   3-2. move(n-1, start, end, mid) -> 마지막 원판 빼고(n-1) 모든 원판을 중간으로 옮긴다. = start에서 mid로 갈거다, end는 보조
   3-3. 시작에서 도착한 부분을 list에 추가해준다.
   3-4. 제일 큰 원판을 3기둥(마지막)으로 옮긴다.
   3-5. move(n-1, mid, start, end) -> 중간에 있는 원판들을 마지막으로 옮긴다.

4. list에 담긴 배열을 answer에 담아서 반환한다.

정답 코드

import java.util.*;
class Solution {
    static ArrayList<int[]> arr = new ArrayList<>();
    public int[][] solution(int n) {
        //시작
        move(n,1,2,3);
        
        int[][] answer = new int[arr.size()][2];
        for(int i=0; i<arr.size(); i++) {
            answer[i] = arr.get(i);
        }
        return answer;
    }
    
    //재귀
    public void move(int n, int start, int mid, int end) {
        //종료조건
        if(n==0) {
            return;
        }
        
        //마지막 원판 빼고 중간으로 몰기
        move(n-1,start,end,mid);
        //list에 담기
        arr.add(new int[]{start, end});
        //중간에서 끝으로 보내기
        move(n-1,mid,start,end);
    }
}

정답! 하노이탑 어렵다 어려워;;

이해를 돕기 위해 gpt에 물어봐서 나온 재귀 결과를 첨부한다 (내가 항상 헷갈린다 머쓱^^)

n=2일때

move(2, 1, 2, 3)
├─ move(1, 1, 3, 2)
│  ├─ move(0, 1, 2, 3)       // 아무 일도 안함
│  ├─ arr.add([1, 2])        // 작은 원판 1을 1→2로 이동
│  └─ move(0, 3, 1, 2)       // 아무 일도 안함
├─ arr.add([1, 3])           // 큰 원판 2를 1→3으로 이동
└─ move(1, 2, 1, 3)
   ├─ move(0, 2, 3, 1)       // 아무 일도 안함
   ├─ arr.add([2, 3])        // 작은 원판 1을 2→3으로 이동
   └─ move(0, 1, 2, 3)       // 아무 일도 안함