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

재귀 문제로 유명한 하노이의 탑

나무위키에 등록될 정도이다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/12946?language=java

프로그래머스

 

알고보니 굉장히 간단한 문제였다.

시작점을 a , 경유지를 b, 목적지를 c라고 하면

원판을 목적지까지 다 옮기기 위해서는 결국 



1. a  지점에서 제일 아래에 존재하는 가장 큰 원반을 제외한 원반들은 b 옮겨져야 한다.

2. 그리고 가장 큰 원반을 c로 옮기고

 3. b에 존재하는 원반들을 a 지점을 경유지로 두고 c로 옮겨야 한다.

1,2,3의 과정을 모두 수행하는 곳이 move 함수가 되는 것이다.

이걸 move 함수로 보면 a가 start, b가 tmp, c가 end가 된다.

 

 

import java.util.*;
class Solution {
    private static List<int[]> arr = new ArrayList<>();

    public int[][] solution(int n) {
        move(1,2,3,n);
        int[][] answer = arr.stream()
                .toArray(int[][]::new);

        return answer;
    }
    
    private static void move(int start, int tmp, int end, int cnt) {
         if(cnt == 0) {
             return;
         }
        move(start, end, tmp, cnt-1);
        arr.add(new int[]{start,end});
        move(tmp, start, end, cnt-1);
    }
}