이제 solution() 메서드에서 n개의 원판을 기둥 1에서 기둥 3으로 옮기는 과정을 재귀 메서드로 다음과 같이 구할 수 있습니다.
public int[][] solution(int n) {
return hanoi(n, 1, 3).toArray(new int[0][]);
}
이렇게 재귀를 이용하면 복잡할 것 같은 하노이의 탑 문제도 간단하게 구현할 수 있습니다.
전체 코드
5장/하노이의_탑.java
import java.util.ArrayList;
import java.util.List;
public class Solution {
private List<int[]> hanoi(int n, int from, int to) {
if (n == 1) return List.of(new int[] {from, to});
int empty = 6 - from - to;
List<int[]> result = new ArrayList<>();
result.addAll(hanoi(n–1, from, empty));
result.addAll(hanoi(1, from, to));
result.addAll(hanoi(n–1, empty, to));
return result;
}
public int[][] solution(int n) {
return hanoi(n, 1, 3).toArray(new int[0][]);
}
}