프로그래머스 하노이의 탑(JAVA)

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

코딩테스트 연습 - 하노이의 탑

 

 저는 재귀를 통해 해당 문제를 해결하였습니다.

전체를 3으로 이동시키기 위해서는 맨 밑을 제외한 것을 모두 2에 옮겨야하고 맽 밑을 3으로 옮겨야합니다.

이 위층 또한 같은 매커니즘입니다. 맨 밑을 제외한 것을 모두 2에 옮기려면 맨 밑에서 2개를 제외한 것을 3으로 옮겨야합니다.....

위의 로직을 재귀를 통해 구현하였습니다.

 

import java.util.*;
class Solution {
    public int[][] solution(int n) {
        int[][] answer = {};
        List<int[]> result = new ArrayList<>();
        hanoi(n,1,2,3,result);
        answer = new int[result.size()][];
        for(int i = 0 ; i < result.size(); i++){
            answer[i] = result.get(i);
        }
        return answer;
    }
    private void hanoi(int depth, int from,int temp,int to,List<int[]> result){
        if(depth == 0){
            return ;
        }
        hanoi(depth-1,from,to,temp,result);
        result.add(new int[] {from,to});
        // System.out.println(from+"->"+to);
        hanoi(depth-1,temp,from,to,result);
    }
}