[JAVA] 하노이의 탑 - 프로그래머스[Lv.1]

https://school.programmers.co.kr/learn/courses/30/lessons/12946

프로그래머스

---

import java.util.*;

class Solution {
    static List<int[]> move = new ArrayList<>();
    
    public int[][] solution(int n) {
        hanoi(n, 1, 3, 2);
        int[][] answer = new int[move.size()][2];
        for(int i = 0; i < move.size(); i++){
            answer[i] = move.get(i);
        }
        return answer;
    }
    
    private void hanoi(int n, int start, int end, int via) {
        if(n == 1) {
            move.add(new int[]{start, end});
            return;
        }
        hanoi(n-1, start, via, end);
        move.add(new int[]{start, end});
        hanoi(n-1, via, end, start);
    }
}

💡 재귀

풀이

하노이의 탑은 대표적으로 재귀를 활용한 문제. 헷갈려서 정리해 놓는다..

가정 : n개의 원판, 3개의 기둥(1, 2, 3) 존재. 1번 기둥 - 3번 기둥으로 옮긴다고 가정

 

🔻 원판 옮기는 대략적 흐름

 1. 1 ~ n-1번째 원판을 2번 기둥으로 옮긴다.

 2. n번째 원판을 3번 기둥으로 옮긴다.

 3. n-1개의 원판을 2번에서 3번으로 옮긴다.

 

✅ IF) 원판 3개를 옮기는 경우

   (1) 1 → 3 [1번째 원판]

   (2) 1 → 2 [2번째 원판]

   (3) 3 → 2 [1번째 원판]

   ➡️ 2(N-1)개를 1 → 2 기둥으로 옮김

   (4) 1 → 3 [3번째 원판] >> 3번째 원판 옮김

   ➡️ 1개를 1→ 3 기둥으로 옮김

   (5) 2 → 1 [1번째 원판]

   (6) 2 → 3 [2번째 원판] >> 2번째 원판 옮김

   (7) 1 → 3 [1번째 원판] >> 1번째 원판 옮김

   ➡️ 2(N-1)개를 2 → 3 기둥으로 옮김

🎯 즉, 원판을 N개 1 → 3으로 옮기기 위해선, N-1개 1→2 이동 + 1개 1 →3 이동 + N-1개 2→3 이동이 필요함
    ⇒ hanoi(N, start, end, via) = hanoi(N-1, start, via, end) + move(start, end) + hanoi(N-1, via, end, start)가 됨

 

➕ 재귀 함수일 경우 반드시 탈출 조건을 설정해야 하므로, n = 1인 경우 return 하도록 설정해야 함