프로그래머스 - 하노이 탑

코드

import java.util.*;
import java.util.stream.*;

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

    public int[][] solution(int n) {
        int[][] answer = {};

        hanoi(n,1,3,2);

        return  list.stream().map(i -> i).toArray(int[][]::new);
    }

    public void hanoi(int count, int from , int to,int empty) {

        if (count == 1) {
            list.add(new int[]{from,to});
            return;
        } 


        hanoi(count-1,from,empty,to);
        hanoi(1,from,to,empty);
        hanoi(count-1,empty , to ,from);

    }

}

풀이

🤔예전부터 풀어보고 싶었지만 너무 막막해서 풀지 못한 것을 이번 기회에 풀어보았다.
재귀로 푸는 것은 알고 있었지만 그 외에는 아무것도 몰랐기에 막막하였다. 그래서 n =2 , n= 3, n=4 일때의 경우의 수를 직접 그려보았는데 n=4의 경우를 그리다 보니 마치 dp비슷한 구조를 보이는 것을 보았다(완전 같지는 않지만 느낌이 비슷했다.)
n=3일 경우 -> n=2의 구조와 함께 마지막 큰 원판을 이동시키는 과정
n=4일 경우 -> n=3의 구조와 함께 마지막 큰 원판을 이동시키는 과정
위와 같은 규칙을 찾아낸 후 계속 보다 보니 재귀의 형태를 보이는 것을 확인 할 수 있었다.
하노이탑 문제를 작은 단위로 분해하는 과정을 보면

1. 큰 원판을 제외한 나머지 원판을 empty로 이동 시키느 과정을 보낸다.
2. 큰 원판을 목표 위치인 to로 이동시킨다.
3. 현재 empty로 옮겨진 원판을 to로 옮기는 과정을 거친다.

😎이렇게 3가지 과정으로 보낼 수 있다. 이때 이 재귀 함수의 종료 조건은 count==1인 경우인데 이 경우는 마지막 원판이 이동하는 과정을 의미한다.
위 문제는 과정을 구하는 문제이기 때문에 원판을 옮기는 순서도 중요하다. 위 과정대로 구현한다면 순서를 맞출 수 있다.

재귀로 푸는 것을 알고는 있었지만 그래도 만만치 않은 문제였다.

출처 : 프로그래머스 - 하노이 탑