[프로그래머스] 하노이의 탑 - Java(자바)

 

문제 이해

• 하노이의 탑은 재귀함수 대표 문제이다.
• 하노이탑의 핵심은 크기가 N인 원반을 시작 점에서 목표 점으로 옮기기 위해서는, 크기가 N-1인 원반을 보조 점으로 먼저 옮기는 것이다.
• from -> other 로 옮기고 other -> to로 이동하는 재귀함수로 반복하여 리스트에 담으면 된다.

import java.util.*;
class Solution {
    static List<int[]> list = new ArrayList();
    public int[][] solution(int n) {        
        hanoi(n,1,3,2);
        
        int[][] answer = new int[list.size()][2];
        for(int i = 0; i<list.size(); i++){
            answer[i][0] = list.get(i)[0];
            answer[i][1] = list.get(i)[1];
        }
        
        return answer;
    }
    
    static void hanoi(int number, int from, int to, int other){
        if(number == 0) return;
        hanoi(number-1,from,other,to);
        int[] temp = new int[2];
        temp[0] = from;
        temp[1] = to;
        list.add(temp);
        hanoi(number-1,other,to,from);
    }
}