프로그래머스 연습문제 하노이의탑 [JAVA] - 23년 3월 13일

하노이탑 참 애증의 문제다.

저번에 공부할때 정말 열심히 이해하고 풀었는데 간만에 다시 푸니까 하나도 기억이 안난다 ㅎㅎ...

대신 이번에 또 한참 고민해서 이제는 다시는 안까먹겠다 다짐을 속으로 해본다 ...

핵심 (n개의 원반을 옮기는 법)
1. n개의 원반을 옮기기 위해서는 n-1개의 원반을 빈 자리로 보내야 한다.
2. n-1개의 원반이 이미 빈자리로 갔으므로 남아있는 1개의 원반은 간단하게 목표하는 자리로 보낼수 있다.
3. n-1개의 원반을 다시 목표하는 자리에 올려둬야 우리가 원하는 하노이 탑을 완성할 수 있으므로 옮긴다.

import java.util.ArrayList;

class Solution {

    private final int START = 1;
    private final int END = 3;
    private int TOTAL_VALUE = 1 + 2 + 3;
    private ArrayList<int[]> answerList;

    public int[][] solution(int n) {
        this.answerList = new ArrayList<>();

        hanoi(n);

        return answerList.toArray(new int[0][0]);
    }

    private void hanoi(int blockNum) {
        hanoiMove(blockNum - 1, START, TOTAL_VALUE - START - END);
        hanoiMove(1, START, END);
        hanoiMove(blockNum - 1, TOTAL_VALUE - START - END, END);
    }

    private void hanoiMove(int num, int from, int to) {
        if (num == 1) {
            this.answerList.add(new int[]{from, to});
            return;
        }

        hanoiMove(num - 1, from, TOTAL_VALUE - from - to);
        hanoiMove(1, from, to);
        hanoiMove(num - 1, TOTAL_VALUE - from - to, to);
    }
}