[백준/BOJ] 12946 하노이의 탑 - JAVA - Lv2

[백준/BOJ] 12946 하노이의 탑 - JAVA - Lv2

문제

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

 

문제 분석

조건

• 한 번에 한 개의 원판만 옮길 수 있다. 
• 큰 원판이 작은 원판 위에 올라갈 수 없다.
• 세 개의 기둥을 이용해 모든 원판을 시작 기둥에서 목표 기둥으로 옮겨야 한다.

풀이방법

• 원판이 1개일 경우, 시작 기둥에서 목표 기둥으로 바로 옮긴다.
• 원판이 N개일 경우, 가장 큰 N번 원판을 목표 기둥으로 옮기기 위해 다음을 반복한다.
  1. N-1개의 원판을 보조 기둥으로 옮긴다.
  2. N번 원판을 목표 기둥으로 옮긴다.
  3. 보조 기둥에 있던 N-1개의 원판을 목표 기둥으로 옮긴다.
• 이 과정을 재귀적으로 반복하여 모든 원판을 이동시킨다.

코드

import java.util.*;

class Solution {
    static List<int[]> list;
    public int[][] solution(int n) {
        
        list = new ArrayList<>();
        hanoi(n,1,2,3);
        int[][] answer = new int[list.size()][2];
        for(int i = 0; i < list.size(); i++){
            answer[i] = list.get(i);
        }
        return answer;
    }
    
    public void hanoi(int n, int from, int use, int to){
        if(n == 1){
            list.add(new int[]{from, to});
        }else{
            hanoi(n-1, from, to, use);
            hanoi(1, from, use, to);
            hanoi(n-1, use, from, to);
        }
    }
}

결과