프로그래머스 - 하노이의 탑(Java)

dfs 문제입니다.

 

하노이의 탑은 큰 원판이 작은 원판 위로 올라갈 수 없다는 특징이 있습니다.

이러한 조건으로 1번 위치의 원판을 모두 3번 위치로 옮겨 그 과정을 반환하는 문제입니다.

 

하노이의 탑은 다음과 같이 일반화할 수 있습니다.

• 1번의 n개 중 n-1개를 2번으로 옮긴다.
• 1번의 가장 큰 n을 3번으로 옮긴다.
• 2번의 n-1개를 3번으로 옮긴다.

 

일반화된 조건에 재귀로 구현만 하면 끝나는 문제입니다.

 

[구현 코드]

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

class Solution {
    private static List<int[]> ansList;

    public static int[][] solution(int n) {

        ansList = new ArrayList<>();
        dfs(n, 1,3, 2);


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

        return answer;
    }

    private static void dfs(int n, int start, int to, int mid) {
        if(n == 1){
            ansList.add(new int[]{start, to});
            return;
        }
        // 1번 기둥의 n-1개를 3번을 걸쳐 2번으로 이동시킴
        dfs(n-1, start, mid, to);

        // 가장 큰 n을 1에서 3으로 이동시킴
        ansList.add(new int[]{start, to});

        // 2번의 기둥의 n-1개를 1번을 걸쳐 3번으로 이동시킴
        dfs(n-1, mid, to, start);
    }
}