하노이의 탑

import java.util.*;
class Solution {
    private static ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
    private static Stack<Integer>[] st = new Stack[4];
 
    public static void hanoi(int n, int from, int to, int via) {
        ArrayList<Integer> move = new ArrayList<Integer>();
        if (n == 1) {
            move.add(from);
            move.add(to);
            list.add(move);
            st[to].push(st[from].pop());
 
        } else {
            hanoi(n - 1, from, via, to);
            move.add(from);
            move.add(to);
            list.add(move);
            st[to].push(st[from].pop());
            hanoi(n - 1, via, to, from);
        }
    }
    public int[][] solution(int n) {
        int[][] answer = {};
        // 스택 초기화
        for (int i = 1; i <= 3; i++)
            st[i] = new Stack<Integer>();
        for (int i = n; i >= 1; i--)
            st[1].push(i);
 
        hanoi(n, 1, 3, 2);
        // move 기록 변환
        answer = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i).stream().mapToInt(Integer::intValue).toArray();
        }
        return answer;
    }
}

하노이의 탑 작동 방식을 재귀로 구현한 것이다.

저런 공식이 나오는 것은 n의 값을 특정지어 직접 테스트 하는 과정에서 도출할 수 있다.

 

참고 사이트가 많은 도움이 되었다.

내용이 가물가물 하다면 반드시 참고하자.

참고 사이트 : https://shoark7.github.io/programming/algorithm/tower-of-hanoi