[재귀] 하노이의 탑(실패분석 - 아이디어)

접근

하노이의 탑

이 문제에 대해서는 재귀로 풀어야 하는 것에 대해서도 떠올리지 못했습니다.
다른 분의 풀이를 보고 재귀임을 알아차렸습니다.

보면 규칙이 존재합니다.

만약 원반이 3개의 경우에는

위와 같은 흐름으로 흘러갑니다.
1. 보면 midle에 n-1개로 하노이의 탑을 만들고
2. start에 남은 가장 큰 원반을 destination으로 옮깁니다.
3. 그리고 middle에 만들어진 하노이의 탑이 시작점이 되어 destination에 하노이의 탑을 만들어 갑니다.

따라서 풀이는 다음과 같습니다.

풀이

import java.util.*;
class Solution {
    static ArrayList<Order> answer;
    
    static class Order{
        int s;
        int e;
        public Order(int s, int e){
            this.s =s;
            this.e=e;
        }
    }
    
    public int[][] solution(int n) {
        answer = new ArrayList<>();
        
        makeHonoi(n,1,3,2);
        
        int[][] result = new int[answer.size()][2];
        // list에 담긴 것을 array에 옮기기
        for(int i=0;i<answer.size();i++){
            result[i][0]=answer.get(i).s;
            result[i][1]=answer.get(i).e;
        }
        
        return result;
    }
    
    static void makeHonoi(int n, int start, int dest, int middle){
        if(n==1) answer.add(new Order(start,dest));
        else{
            // 1.  midle에 n-1개로 하노이의 탑
            makeHonoi(n-1,start,middle,dest);
            // 2. 시작점에 남은 가장 큰 원반을 도착점에
            answer.add(new Order(start,dest));
            // 3. 1번 과정으로 쌓여진 하노이의 탑을 destination에 옮기기
            makeHonoi(n-1,middle,dest,start);
        }
    }
    
}