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

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

프로그래머스

접근 방법

1. 재귀 알고리즘의 스테디 셀러 문제이며, 구현 과정은 다음과 같이 일반화를 통해 풀 수 있다.
2. n-1개의 원판을 1번 기둥 -> 2번 기둥으로 옮긴다
3. 1개 (가장 큰) 원판을 1번 기둥 -> 3번 기둥으로 옮긴다.
4. n-1개의 원판을 2번 기둥 -> 3번 기둥으로 옮긴다

코드

class Solution {
    int[][] ans;
    int idx = 0;
    public int[][] solution(int n) {
        ans = new int[(int) Math.pow(2,n)-1][2];
        
        hanoi(n,1,3);
        return ans;
    }
    
    void hanoi(int n, int from, int to){
        if(n == 1){
            ans[idx][0] = from;
            ans[idx++][1] = to;
            return;
        }
        int o = 6-from-to;
        
        hanoi(n-1, from, o);
        hanoi(1, from, to);
        hanoi(n-1, o, to);
        
    }
}