mingssssss

1. 문제

2. 코드

import java.util.*;

class Solution {
    
    static ArrayList<int[]> list;
      
    public int[][] solution(int n) {
        list = new ArrayList<>();

        dfs(n, 1, 2, 3);
        
        int[][] answer = new int[list.size()][2];
        
        for (int i = 0; i < list.size(); i++) {
            
            int[] arr = list.get(i);
            
            answer[i][0] = arr[0];
            answer[i][1] = arr[1];
        }
                
        return answer;
    }
    
    private static void dfs(int n, int start, int mid, int end) {
        
        if (n == 1) {
            move(start, end);
        } else {
            
            dfs(n - 1, start, end, mid);
            move(start, end);
            dfs(n - 1, mid, start, end);
        }
        
        
        
    }
    
    private static void move(int start, int end) {
        
        list.add(new int[] {start, end});
    }
}

3. 리뷰

한 번쯤 들어본 하노이의 탑을 구현하는 문제이다.

스킬 체크 문제 중에 풀게 되었는데, 도저히 어떻게 풀어야 할지 감이 안 잡히는 문제였다.

처음엔 작은 원판 위에 큰 원판이 올 수 없다는 조건에 꽂혀서

원판이 이동할 때마다 원판의 크기를 기둥의 배열에 입력하는 형식으로 풀었는데

이렇게 풀면 구현이 너무 어려워서 구선생님의 도움을 받았다.

재귀로 구현해야 하는 문제이다.

문제의 개념을 잘 설명해놓은 블로그가 있어서 링크를 남긴다.

https://shoark7.github.io/programming/algorithm/tower-of-hanoi

결국 핵심은 가장 큰 원반이 나올 때 까지 재귀를 수행해야 하고,

가장 큰 원반이 나오면 그 원반을 목적지인 3번 기둥에 놓아야 한다.

가장 큰 원반이 나오기까지 2번 기둥에 원반을 놓아야 한다.

따라서 출발지인 1번 기둥(start), 경유지인 2번 기둥(mid), 도착지인 3번 기둥(end)

가 필요하다. 이 세 개의 인자를 가지고 재귀를 돌려줘야 한다.

가장 큰 원반이 나온 경우(n == 1), move라는 함수를 호출해서

start기둥에서 end 기둥으로 이동했다는 표시를 해준다.

또한 start 기둥에서 end 기둥으로 이동하고 재귀가 끝난 경우에도

move 함수를 호출하여 start에서 end로 이동했다는 표시를 해준다.

재귀가 끝났다면, 모든 원반이 이동한 경우이므로,

list에 저장한 내용을 answer에 넣어주어서 결괏값을 return한다.

구선생님의 도움을 받기 전에는 무조건 원반의 사이즈를 체크해서

현재 이동하는 원반의 크기가 이미 기둥에 놓여져있는 원반의 크기보다 크다면

이동할 수 없는 식의 코드를 짜야 한다고 생각했는데,

재귀를 이용해서 풀어보니 이동할 수 있는 경우의 조건만 move함수를 통해

list에 넣어주면 돼서 간단하게 해결할 수 있었다.

코드 자체는 간단하지만, 출발지와 경유지와 도착지 각각의 기둥을 인자로 가지고 다니면서

dfs 함수를 구현하는 것이 너무 어렵다..

dfs는 정말 함수 호출부터 종료 조건까지 완벽히 이해할 수 있어야

내 것으로 되는 것 같다.