[프로그래머스,자바] Level2: 하노이의 탑

 

문제분석

 

하노이의 탑 문제다. 

 

하노이의 규칙은 한번쯤은 다 알것이다.

 

간단하게 하노이의 규칙의 갯수만 물어보면 매우 쉬운 문제가 되엇겠지만,

 

이동경로까지 전부 구해야한다.  즉, 하노이의 탑 알고리즘을 구해야한다.

 

 

 

하노이의 탑 알고리즘:

 

하노이의 탑은   N개의 원반을  끝지점에 옮기려면, 

 

1.N-1개의 원반을 중간에 놓는다.

2. 가장큰 원반을 끝지점에 옮긴다.

3. 중간에 있는 N-1개의 원반을 끝지점에 옮긴다. 

 

자 무엇이 보이는가 그렇다 DP(점화식)가 보인다.

 

즉 원반을  1-> 2-> 3 경로로 옮기려면,

 

h(1,2,3,N) =  h(1, 3, 2, n-1) {1번과정} + 1 {2번과정} + h(2,1,3) { 3번과정}  이 필요하다.

 

문제풀이

import java.util.*;
class Solution {
    List<int[]> list = new ArrayList<>();
    
    public List<int[]> solution(int n) {
        
        //하노이의 탑 원리
        // N개의 원판이 존재한다고가정
        // h(1, 2, 3 ,N) = h(1,3,2,N-1) + 1 (가장큰원판 깔기) + h(2,1,3,N-1)
        // 점화식 구현 
        
        h(1,2,3,n);
            
        return list;
    }
    
    public void h(int s, int m, int e,int n){
        int[] move = {s,e};
        
        if(n==1){
            list.add(move);
            return;
        }
        else{
            h(s,e,m,n-1);
            list.add(move);
            h(m,s,e,n-1);
        }
    }
}