[JAVA/자바][프로그래머스 12946] 하노이의 탑

문제

---

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

프로그래머스

 

 

접근 방법

---

"하노이의 탑"은 규칙이 존재하는 대표적인 재귀 문제다.

점화식을 세워서 설계하면 쉽게 구현할 수 있다.

(출발지, 경유지, 도착지) 3개의 위치를 선언한다.

"N개, 출발지 -> 도착지"의 경우

"N-1개, 출발지 -> 경유지" + "1개, 출발지 -> 도착지" + "N-1개, 경유지 -> 도착지"의 규칙을 가진다.

이를 점화식으로 표현하고 코드로 구현한다.

 

 

풀이

---

1. 이동 정보를 저장할 자료형 List<int[]> arr 을 선언한다.
2. 이동을 의미하는 메소드 move(int cnt, int start, int mid, int end){} 를 선언한다.
   • cnt개를 start에서 end로 이동한다(필요 시 mid를 경유하며)
     • cnt : 이동할 원판 개수
     • start : 출발지
     • mid : 경유지
     • end : 도착지
3. 재귀를 이용한 점화식을 작성한다.
   • move(cnt - 1, start, end, mid);
   • arr.add(new int[]{start, end});
   • move(cnt - 1, mid, start, end);

4. 코드를 완성한다.

 

 

코드

---

import java.util.*;

class Solution {
    private static List<int[]> arr = new ArrayList<>();

    public int[][] solution(int n) {
        move(n, 1, 2, 3);
        int[][] answer = arr.stream()
                .toArray(int[][]::new);
        return answer;
    }

    private static void move(int cnt, int start, int mid, int end) {
        if (cnt == 0) {
            return;
        }
        move(cnt - 1, start, end, mid);
        arr.add(new int[]{start, end});
        move(cnt - 1, mid, start, end);
    }
}