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

문제

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

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

 

접근법

하노이 탑이 재귀의 대표적인 예시임에도 풀기가 힘들었다.

https://shoark7.github.io/programming/algorithm/tower-of-hanoi

'하노이의 탑' 이해하기

위 블로그를 참고하며 풀었다.

재귀(recursion)란 같은 형태의 보다 작은 입력을 지닌 자기 자신을 호출하는 것이고, 이렇게 재귀적인 호출을 사용하는 함수를 재귀함수라고 한다. 

n이 1일때는 그냥 원판을 출발지에서 도착지로 옮긴다

n이 1보다 큰 경우에는

1. 출발지에 있는 n-1개의 원판들을 경유지로 옮긴다.

2. 출발지에 있는 가장 큰 원판을 도착지로 옮긴다.

3. 경유지에 있는 n-1개의 원판들을 도착지로 옮긴다.

 

n개의 원판을 옮기는데 필요한 이동 횟수는 2^n - 1이다.

 

코드

import java.util.ArrayList;
import java.util.List;

class Solution {
    List<int[]> list;
    public int[][] solution(int n) {
        list = new ArrayList<>();

        dfs(n, 1, 3, 2);

        int[][] answer = new int[list.size()][2];

        for(int i=0;i<list.size();i++){
            int[] arr = list.get(i);
            answer[i][0] = arr[0];
            answer[i][1] = arr[1];
        }
        return answer;
    }

    private void dfs(int n, int from, int to, int mid) {
        if(n==1)
            move(from, to);
        else{
            dfs(n-1, from, mid, to);
            move(from, to);
            dfs(n-1, mid, to, from);
        }
    }

    private void move(int from, int to){
        list.add(new int[]{from, to});
    }
}