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

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

programmers.co.kr/learn/courses/30/lessons/12946

코딩테스트 연습 - 하노이의 탑

 

풀이

DP의 전형적인 문제인 하노이의 탑 문제이다.

 

하노이의 탑은 문제 설명에도 나와있듯이 N개의 원판을 1번 기둥에서 3번 기둥으로 2번 기둥을 사용하여 조건에 맞게 이동시키는 문제이다.

 

이 문제를 이해하기 위해 N이 작은 때를 생각해 보았다. N이 2라면 2개의 원판을 1 -> 2 -> 3으로 옮기는 경우의 수가 될 것이고 이는 작은 원반을 2로 먼저 옮기고 큰 원반을 3에 옮긴 후 2에 있는 원반을 3으로 옮기는 것이다. 그림으로 보면 다음과 같다. 

이와 같이 N개의 원반을 1 -> 2 -> 3으로 옮기는 것은 N - 1개의 원반을 1 -> 2로 먼저 옮기고, 마지막 제일 큰 원반을 1 -> 3으로 옮긴 다음, 나머지 2에 있는 원반들을 2 -> 3으로 옮기는 것과 같다. 

 

즉, hanoi(1, 2, 3, n) = hanoi(1, 3, 2, n - 1) + 1에 있는 제일 큰 원반을 3으로 옮긴다.(1) + hanoi(2, 3, 1, n - 1)과 같다.

위 식을 해석하면 N개의 원반을 1 -> 2 -> 3으로 옮기는 경우는 N-1개의 원반을 1 -> 3 -> 2로 옮긴후 제일 큰 원반을 3으로 옮긴 후  N-1개의 원반을 2 -> 1 -> 3으로 옮기는 것이다.

 

코드

import java.util.*;
 
class Solution {
    
    ArrayList<int[]> list;
    
    public int[][] solution(int n) {
        list = new ArrayList<>();
        hanoi(1, 2, 3, n); //n개의 원판을 1에서 시작 -> 2를 거쳐 -> 3으로 옮긴다.
        int[][] result = new int[list.size()][2];
        for(int i = 0; i < list.size(); i++) {
            result[i][0] = list.get(i)[0];
            result[i][1] = list.get(i)[1];
        }
        return result;
    }
    
    public void hanoi(int s, int v, int e, int n) {
        int[] move = {s, e};
        
        if(n == 1) list.add(move);
        else {
            hanoi(s, e, v, n - 1);
            list.add(move);
            hanoi(v, s, e, n - 1);
        }
    }
}