[프로그래머스] 하노이의 탑

import java.util.ArrayList;

class Solution {
    public void hanoi(int n, int now, int to, int temp, ArrayList<int[]> answer){
        if(n==1) answer.add(new int[]{now, to});
        else{
            hanoi(n-1,now,temp,to,answer);
            answer.add(new int[]{now, to});
            hanoi(n-1,temp,to,now,answer);
        }
        
    }
    public int[][] solution(int n) {
        // int[][] answer;
        ArrayList<int[]> answerList = new ArrayList<>();
        //홀수면 3으로 시작, 짝수면 자신과 다른 값(1or2)로 시작
        hanoi(n,1, 3, 2, answerList);
        int[][] answer = new int[answerList.size()][2];
        for (int i = 0; i < answerList.size(); i++) {
            answer[i] = answerList.get(i);
        }
        return answer;
    }
}

n은 옮겨야 할 원판의 수
now는 현재 막대
to는 옮기려고 하는 막대
temp는 임시 막대
보조 막대로 먼저 옮기는 것을 재귀로 푸는 것이 핵심이다
(now->temp) -> (temp->to)를 하면 (now->to)에 해당하는 값을 얻을 수 있다.

깔끔한 버전

class Solution {
    private int index = 0;
        public int[][] solution(int n) {
            int[][] answer = new int[(int) (Math.pow(2,n)-1)][2];

            move(n, 1, 3, 2, answer);
            return answer;
        }

        public void move(int n, int start, int end, int between, int[][] answer) {
            if (n == 1) {
                answer[index++] = new int[]{start, end};
                return;
            }
            move(n - 1, start, between, end, answer);
            answer[index++] = new int[]{start, end};
            move(n - 1, between, end, start, answer);
        }
}