앞의 코드를 살펴보면 점화식에 따라 상태는 이전과 똑같이 전이됩니다. 다만 차이점은 과정을 이어 붙이는 방식입니다. 이전에는 List를 반환하고 이를 모두 이어 붙였는데, 이 코드는 하나의 List에 과정을 기록하므로 쓸데없이 이미 구한 과정을 다시 순회하는 일은 발생하지 않습니다.
이렇게 hanoi() 메서드가 수정되면서 solution() 메서드도 다음과 같이 수정됩니다.
public int[][] solution(int n) {
List<int[]> process = new ArrayList<>();
hanoi(n, 1, 3, process);
return process.toArray(new int[0][]);
}
최적화가 모두 적용된 전체 코드는 다음과 같습니다.
전체 코드
5장/하노이의_탑_최적화.java
import java.util.ArrayList;
import java.util.List;
public class Solution {
private void hanoi(int n, int from, int to, List<int[]> process) {
if (n == 1) {
process.add(new int[] {from, to});
return;
}
int empty = 6 - from - to;
hanoi(n–1, from, empty, process);
hanoi(1, from, to, process);
hanoi(n–1, empty, to, process);
}
public int[][] solution(int n) {
List<int[]> process = new ArrayList<>();
hanoi(n, 1, 3, process);
return process.toArray(new int[0][]);
}
}