[programmers] 하노이의 탑

09 Apr 2023 in Algorithm on Algorithm

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

쪽팔리지만.. 이해하는데 1주일은 걸린것 같다..

https://vidkidz.tistory.com/649

위 링크에서 시뮬레이션 결과 n=4까지 아래와 같이 나왔다.

n=4	n=3	n=2
1,2	1,3	1,2
1,3	1,2	1,3
2,3	3,2	2,3
1,2	1,3
3,1	2,1
3,2	2,3
1,2	1,3
1,3
2,3
2,1
3,1
2,3
1,2
1,3
2,3

여기서 발견된 공통점

• 무조건 홀수에 중간은 1,3 이동이 있다
• 이 중간을 기준으로 N-1 하노이가 반복된다
• 윗쪽 N-1 하노이는 N-1 전체가 1번에서 2번으로 이동 하는 로직
• 아랫쪽 N-1 하노이는 N-1 전체가 2번에서 3번으로 이동 하는 로직

회고) 결과를 토대로 유추를 할때는 결과 출력을 해보고 공통점을 발견해보자..

import java.util.*;

class Solution {
    public int[][] solution(int n) {
        List<int[]> moves = new ArrayList<>();
        hanoi(n, 1, 3, 2, moves);

        int[][] answer = new int[moves.size()][2];
        for (int i = 0; i < moves.size(); i++) {
            answer[i] = moves.get(i);
        }

        return answer;
    }

    private void hanoi(int n, int from, int to, int via, List<int[]> moves) {
        if (n == 1) {
            moves.add(new int[]{from, to});
            return;
        }

        hanoi(n - 1, from, via, to, moves);   // Step 1
        moves.add(new int[]{from, to});       // Step 2
        hanoi(n - 1, via, to, from, moves);   // Step 3
    }
}