[프로그래머스] 하노이의 탑 - Java [자바]

 

📜 문제 내용

 

🤔 과정

• 간단하게 과정을 줄이면 시작 기둥의 맨 아래에 있는 가장 큰 원판을 제외한 나머지 n - 1개의 원판을 중간 기둥에 옮긴다.
• 그리고 나서 마지막 맨 아래 가장 큰 원판을 끝 기둥에 옮긴다. 
• 마지막으로 중간 기둥에 있는 n - 1 개의 원판을 끝 기둥으로 옮긴다. 

 

✨ 최초 제출 답안

import java.util.*;
import java.io.*;

class Solution {
    // int 배열을 원소로 갖는 List 생성
    public static List<int[]> list;
    
    // n 개 원판, 시작 기둥 st, 중간 기둥 mid, 끝 기둥 ed
    public static void dfs(int n, int st, int mid, int ed){
        // 원판이 하나 남았으면 마지막 한 개를 list에 저장
        if(n == 1){
            list.add(new int[]{st, ed});
            return;
        }
        
        // n-1개 원판을 시작 기둥에서 중간 기둥으로 옮기기
        dfs(n - 1, st, ed, mid);
        
        // 가장 큰 마지막 원판을 시작 기둥에서 끝 기둥으로 옮기기
        list.add(new int[]{st, ed});
        
        // n-1개 원판을 중간 기둥에서 끝 기둥으로 옮기기
        dfs(n - 1, mid, st, ed);
    }
    
    public int[][] solution(int n) {
        list = new ArrayList<>();
        dfs(n, 1, 2, 3);
        
        int[][] answer = new int[list.size()][];
        for(int i=0;i<list.size();i++){
            answer[i] = list.get(i);
        }
        return answer;
    }
}

 

🔗 문제 링크

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

프로그래머스