[프로그래머스] 하노이의 탑

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12946

프로그래머스

접근 방법 및 풀이

재귀의 가장 대표적인 예

n개의 원판을 목표 기둥으로 옮기기 위해서는 n번째를 옮기기 전에 1번째부터 n - 1번째까지의 원판이 남은 기둥에 모두 옮겨져 있어야 n번째 원판을 목표 기둥으로 옮길 수 있음

그리고 남은 기둥에 옮겨져 있던 1번째부터 n - 1번째까지의 원판을 목표 기둥의 n번째 원판 위로 옮겨야 함

재귀 함수의 구분을 1번째부터 n - 1번째까지의 묶음과 n번째 원판 하나의 묶음, 이렇게 두개의 묶음으로 고려

import java.util.ArrayList;
import java.util.List;

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

        dfs(n, 1, 3, 2);

        int[][] answer = new int[list.size()][];
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }
        return answer;
    }

    private void dfs(int n, int start, int end, int temp) {
        // 종료 조건
        if (n == 1) {
            list.add(new int[]{start, end});
            return;
        }

        // n번째 위의 1번째부터 n - 1 번째까지 temp로 옮긴다
        dfs(n - 1, start, temp, end);

        // n번째 원판을 end로 이동 시킴
        list.add(new int[]{start, end});

        // temp로 옮겨 놓았던 1번째부터 n - 1번째를 end로 옮김
        dfs(n - 1, temp, end, start);
    }
}