프로그래머스 | LV.2 하노이의 탑 - 재귀 문풀 (Java)

⬛ 프로그래머스 | LV.2 하노이의 탑 - 재귀 문풀 (Java)

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

프로그래머스

---

💚문제 접근 방식

규칙성을 찾아야지 생각은 했지만 재귀로 푸는 거라고는 생각을 못했다… ㅎ

🎈재귀인 이유

A 기둥에 있는 탑을 1개씩 (큰거 위에 작은 거)를 순서대로 옮길 거다.

임시 기둥이 B이고 목표 기둥이 C라고 했을 때 필연적으로 다음의 과정을 거친다.

몇번을 반복할지는 모르지만 n개의 탑이 존재한다고 헀을 때

     A → B : (n-1) 개를 임시 기둥으로 옮긴다.

     A → C : 가장 큰 1개는 목표 기둥으로 (1회) 옮긴다

     B → C : (n-1) 개 있던 임시기둥에서 다시 목표 기둥으로 옮긴다.

//재귀는 n-1개에 대해서 계속 재귀적으로 이루어진다. 

함수 공식이 추려지는데

f(n) = 1 + 2X f(n-1) 이다.

즉, 1번은 가장 큰 거 목표로 옮기기 + (n-1) 개를 순서에 맞춰서 2번 옮기는 것 이다.

 

recursive(cnt, st, mid, ed)       cnt: st→ ed로 이동해야 할 원판 개수       st : 출발지       ed: 도착지       mid = 경유지       재귀를 이용하여 작성한다. recursive(cnt-1, st, ed, mid)

 

💚 제출 코드

import java.util.*;
class Solution {
    private static List<int[]> list = new ArrayList<>();
    //recursive
    private static void recursive(int cnt, int st, int mid, int ed){
        if(cnt == 0) return;
        
        recursive(cnt-1, st, ed, mid);
        list.add(new int[] {st, ed});
        recursive(cnt-1, mid, st, ed);
    }
    
    //솔루션함수 
    public int[][] solution(int n) {
        
        recursive(n, 1, 2, 3);
        int[][] answer = list.stream().toArray(int[][]::new);
        
        
        
        return answer;
    }
}