문제 풀이 최적화

앞의 코드는 하노이의 탑 문제를 잘 풀어내지만 매 부분 문제마다 구해 놓은 과정을 전부 순회하며 이어 붙이기 때문에 효율적이지 않습니다. 하노이의 탑 문제처럼 과정을 전부 기록해야 하는 문제의 답을 메서드의 반환을 이용하여 구하려고 하면 이렇게 비효율적인 구현이 될 수 있습니다.

이 경우에는 메서드의 반환 대신 매개변수를 이용하여 과정을 기록할 수 있습니다. 이 문제는 과정을 List<int[]>로 다루었습니다. 이렇게 과정을 기록하는 변수를 메서드의 매개변수로 넘겨주면 다음과 같이 hanoi() 메서드를 다시 작성할 수 있습니다.

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);
}