[Programmers Lv.3][하노이의 탑][java]

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

프로그래머스

하노이 탑 연습해보기 >> https://www.mathsisfun.com/games/towerofhanoi.html

Play Tower of Hanoi

---

조건

• n은 15이하의 자연수 입니다.
• 기둥 3개, 처음에 작은 것이 위에 있도록 쌓여있음

1. 한 번에 하나의 원판만 옮길 수 있습니다.
2. 큰 원판이 작은 원판 위에 있어서는 안됩니다.

알고리즘

목표 : 1 → 3 으로 최소 횟수로 옮기기

일단 하노이탑 원리에 대해서 찾아봤었다.
n=3일 때, 그림으로 옮겨지는 이미지 보고 이해했다

전체적으로 크게 봤을 때,
n-1 개가 1,3번을 통해 2번으로 옮겨지고, n번째 링이 3번으로 옮겨지고
n-2개가 1,3번을 통해 2번으로 옮겨지고, n-1번째 링이 3번으로 옮겨지고
..
..

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

public class Solution12946 {
    List<int[]> arr = new ArrayList<>();
    public int[][] solution(int n) {
        hanoi(n, 1, 3, 2);
        int[][] answer = new int[arr.size()][2];
        for(int i=0; i < arr.size(); i++) answer[i] = arr.get(i);
        return answer;
    }

    public void hanoi(int n, int start, int end, int mid){
        if(n == 1) arr.add(new int[]{start, end});
        else{
            hanoi(n-1, start, mid, end);
            arr.add(new int[]{start, end});
            hanoi(n-1, mid, end, start);
        }
    }
    public static void main(String[] args) {
        Solution12946 solution12946 = new Solution12946();
        int[][] answer = solution12946.solution(3);
        for(int i=0; i < answer.length; i++){
            System.out.print(Arrays.toString(answer[i]));
        }
    }
}