코드 작성

앞서 정의한 재귀를 이용하여 코드를 작성해봅시다.

먼저 상태를 이용하여 재귀 메서드 hanoi()를 정의합니다. 이 메서드는 부분 문제를 해결해야 하므로 원판의 이동 과정을 반환해야 합니다. 또 하나의 부분 문제는 더 작은 부분 문제들에서 구한 원판의 이동 과정을 모두 이어 붙여야 합니다. 이 과정을 쉽게 수행할 수 있도록 List를 이용하여 이동 과정을 나타내겠습니다.

private List<int[]> hanoi(int n, int from, int to) {
    // 종료 조건, 점화식 구현
}

종료 조건은 n 값이 1일 때 from에서 to로 이동시키는 것만 포함된 과정을 반환하는 것입니다. 이는 다음과 같이 작성할 수 있습니다.

private List<int[]> hanoi(int n, int from, int to) {
    if (n == 1) return List.of(new int[] {from, to});
    
    // 점화식 구현
}