[프로그래머스] 하노이의 탑

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

코딩테스트 연습 - 하노이의 탑

2021-09-06

---

import java.util.*;
class Solution {
    static ArrayList<int[]> list;
    static void hanoi(int n, int from, int to , int via) {
        if(n == 1) {
            list.add(new int[]{from , to});
        } else {
            hanoi(n-1, from, via, to);
            list.add(new int[]{from, to});
            hanoi(n-1, via, to , from);
        }
    }
 
    static int[][] solution(int n) {
        list = new ArrayList<>();
        hanoi(n, 1, 3, 2);
        int[][] answer = new int[list.size()][2];
        for(int i = 0; i < list.size(); i++) {
            answer[i][0] = list.get(i)[0];
            answer[i][1] = list.get(i)[1];
        }
        return answer;
    }
}

#문제풀이

1) n == 1 일 때, 출발지(from)에서 도착지(to)로 바로 넘겨주면 된다.

2) 아닌 경우

  (1) n-1만큼, 출발지(from)에서 경유지(via)에 넘겨준다.

  (2) 남은 판을 출발지(from)에서 도착지(to)로 바로 넘겨준다.

  (3) n-1만큼, 경유지(via)에서 도착지(to)로 넘겨준다.

 

총 횟수는 2^n - 1