프로그래머스 Lv.3) 하노이의 탑

하노이의 탑

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

풀이

문제에서 n이 15이하로 주어졌기 때문에, 메소드 재귀 호출을 이용해 문제를 풀어야겠다는 생각을 했다. 

그리고, 문제 조건을 쭉 써본 결과 n에 대해 최소 이동 횟수는 2^n -1이 된다는 것을 파악했다.

우선, 최소 이동 횟수만큼 result 배열을 만들어 주었다. ( 0 : 원판을 가져온 기둥, 1 : 원판을 옮긴 기둥을 저장해야하기 때문에 2차원 배열)

그리고 이리저리 삽질을 한 것 같다. 재귀로 풀었지만 몇개 문제에서 시간초과가 뜨고, 규칙을 찾아 횟수를 줄이려는 등 많은 시도를 했지만, 결국에는 풀지 못했다.

그래서 검색을 해봤더니, 많은 분들이 하노이의 탑은 학부생 시절에 많이 했던 문제라 어렵지 않게 풀었다는 것이다... 

나는 왜 학부생 시절에 푼 기억이 없지... ㅠㅠ

아무튼, 가장 간결하고 이해하기 쉽게 짠 분의 코드를 보고 해석하는 것으로 문제를 익혔다.

(링크) (따로 허락을 구하지 않고 참고 및 링크를 남겨 죄송합니다, 문제가 된다면 삭제하겠습니다.)

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

하노의 탑의 규칙은, 출발지인 한 기둥에서 목적지인 다른 기둥으로 옮길 때 n-1개 만큼 또 다른 기둥을 경유했다가 목적지 기둥에 넣는 방식이라고 한다. 그래서, 1->2번을 가는 경우에는 1->3->2 순서가 되는 것이고, 2->3으로 가는 경우는 2->1->3 순서가 된다.

hanoi 메소드에 원반의 갯수 N을 넣고, N을 모두 옮길 때까지 반복하며 result 배열에 답을 저장해준다.

 

코드

class Solution {
    int[][] result;
    int idx =0;
    
    public int[][] solution(int n) {
        int size = (int)Math.pow(2,n)-1;
        result = new int[size][2];
        hanoi(n,1,3,2);
        
        return result;
    }
    
    private void hanoi(int n, int start, int dest, int stopOver) {
        if(n ==0) {
            return;
        }
        // 1번 기둥의 n개 원반에서 n-1개 를 2번 기둥으로 옮김(3번 기둥 경유)
        hanoi(n-1,start,stopOver,dest);
        result[idx][0] = start;
        result[idx++][1] = dest;
        
        //2번 기둥의 n-1개의 원반을 3번 기둥으로 옮김(1번 기둥 경유)
        hanoi(n-1,stopOver,dest,start);
    }
}