[Java] 프로그래머스 Level 2 : 하노이의 탑

- 문제설명 & 제한사항

- 예시

- 해결과정

• 작은 문제에서 큰 문제를 해결해나가도록 재귀함수를 호출하자.
  1. n개의 원반을 목적지까지 옮기기 위해서는 n-1개의 원반을 먼저 경유지로 옮긴다.
  2. 남아있는 가장 큰 원반을 목적지로 옮긴다.
  3. 경유지에 있는 n-1개의 원반을 목적지로 옮긴다.
• 재귀 호출의 흐름을 파악하려고 하면 이 문제는 상당히 복잡해진다. 큰 흐름만 살펴보자.
• 1) 원반이 1개인 경우, 즉 가장 작은 상황부터, 이동을 마치고 2개, 3개, 4개, 5개로 확장해서 생각해보자.
  2) 1개의 원반만 있으므로 바로 목적지로 옮길 수 있다. 현재 재귀호출을 종료하고 상위 재귀호출(원반2개)로 돌아간다.
  3) 이전 재귀호출의 입장(원반 1개 이동)에서는 목적지로 원반을 옮긴 것이지만, 현재 재귀호출(원반2개) 입장에서는 n-1개의 원반을 경유지로 옮긴것이다. 이후 남아있는 가장 큰 원반을 목적지로 옮기고, 경유지에 있는 1개의 원반을 목적지로 옮기게 된다.
  4) 2개를 모두 목적지까지 옮기고나서 상위 재귀호출(원반3개)로 넘어가게 되면, 2개(n-1개)를 옮긴것은 경유지로 옮긴것이다. 그럼 현재 재귀호출 입장에서는 남아있는 가장 큰 원반을 목적지로 옮기고 다시 경유지에 있는 2개의 원반을 목적지로 옮기게 되고 현재 재귀호출을 종료하게 된다.
  5) 또 다시 상위 재귀호출(원반4개)로 돌아가보면, 현재까지 목적지로 옮긴 3개의 원반은 경유지로 옮긴것이다.
  6) 반복
• 작은 원반 위에 큰 원반이 오지 않도록 부분 문제들을 설계했기에, 해당 재귀를 거치면 원하는 결과를 얻을 수 있다.  

- 솔루션

import java.util.*;

class Solution {
    
    ArrayList<int[]> list = new ArrayList<>();
    
    public int[][] solution(int n) { 
        move(n, 1, 3, 2);
        return list.toArray(new int[list.size()][2]);
    }
    
    private void move(int n, int start, int end, int except) {
        if(n == 1) {
           list.add(new int[]{start, end});
           return;     // 남아있는 가장 큰 원반 목적지로 옮기기
        }
        else {
            move(n-1, start, except, end);  // n-1개 경유지로 옮기기

            move(1, start, end, except);   // 바로 위 재귀가 끝나면 상위 재귀 입장에서는 가장 큰 원반이
						// 남아있으므로 해당 원반을 목적지로 이동시킨다.
                        
            move(n-1, except, end, start); // 경유지에 있는 원반을 목적지로 이동시킨다.
        }
    }
    
}

- 배운점

• 핵심은 재귀 함수의 흐름을 추적하며 코드를 작성하는 것이 아닙니다.
• 그저 명확한 종료조건, 수행해야 할 동작을 오류 없이 설계하는 것이 중요합니다.