프로그래머스 - 하노이의 탑 - 재귀 - Java

1. 문제

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

2. 풀이

재귀는 언제나 3단계.
1. 상태
2. 종료조건
3. 점화식.

1. 상태
(n, from, to)
n: 옮기려는 원판 개수
from: 원판이 현재 위치한 기둥
to: 원판이 옮겨질 기둥

2. 종료조건
결국 옮길 수 있는 원판이 1개일때 이다.

3. 점화식

1. n-1개의 원판을 from에서 empty(아무것도 없는) 기둥으로 옮긴다.
   이때 empty는 6-from-to이다.
2. 남은 1개의 원판을 from에서 to로 옮긴다.
3. n-1개의 남은 원판을 empty에서 to로 옮긴다.

3. 전체 코드

import java.util.*;

class Solution {
    public int[][] solution(int n) {
        ArrayList<int[]> list = new ArrayList<>();
        hanoi(n, 1, 3, list);
        return list.toArray(new int[0][]);
    }
    
    public void hanoi(int n, int from, int to, ArrayList<int[]> list){
        if(n == 1){
            list.add(new int[]{from, to});
            return;
        }
        
        hanoi(n-1, from, 6-from-to, list);
        hanoi(1, from, to, list);
        hanoi(n-1, 6-from-to, to, list);
    }
}