[Java] 프로그래머스(level-2) - 하노이의 탑

문제 풀이

---

이번 문제는 하노이의 탑 원리를 잘 숙지하고 있으면 풀 수 있는 문제이다.

아이디어 도출

필자는 하노이의 탑 원리를 구현하기 위해 재귀 함수를 이용했다. 또한 이번 문제는 백준에서 출제된 하노이의 탑 이동순서 문제와 굉장히 유사하니 해당 문제를 풀었다면 해당 문제도 쉽게 풀 수 있을 것이다.

재귀를 이용해 하노이의 탑에서 원판을 이동시킬 때, 첫번째 탑에서 두번째 탑으로 이동해야할 N-1개의 원판들은 재귀함수를 통해 원판이 1개가 남을 때까지 이동하게 된다.

문제의 예시처럼 첫번째 탑에 있는 2개의 원판을 마지막 탑으로 최소한의 과정을 통해 옮기기 위해서는 아래와 같은 과정이 필요하다.

1. 첫번째 원판을 시작 탑에서 중간 탑으로 옮긴다.
2. 두번째 원판을 시작 탑에서 마지막 탑으로 옮긴다.
3. 중간 탑에 남아있던 첫번째 원판을 중간 탑에서 마지막 탑으로 옮긴다.

위 과정을 재귀로 풀어내는 방법을 알았으니, 해당 과정에서 일어나는 이동과정을 배열에 담아서 2차원 배열로 반환하면 되는 것이다.

그렇게 문제풀이를 위한 아이디어는 생각해보니 다음과 같았다.

1. n개의 원판을 지정해 하노이 재귀 함수를 호출한다.
2. 재귀 함수를 통해 원판을 시작 탑에서 마지막 탑까지 옮긴다.
3. 원판을 옮기는 과정에서 원판이 어느 탑에서 어느 탑으로 옮겨졌는지에 대한 정보를 담아 2차원 배열 형태로 반환한다.

다음으로 문제 풀이를 위해 작성한 코드는 아래와 같다.

작성 코드

---

import java.util.*;

class Solution {

    // 이동시 첫번째 탑과 
    static ArrayList<int[]> result = new ArrayList<>();

    public int[][] solution(int n) {
        /**
         * 3개의 탑을 두고 하노이 함수 실행
         * 첫번째 탑에 n개의 원판이 존재한다.
         */
        hanoi(1, 2, 3, n);

        // Stream을 활용해 ArrayList<int[]> 타입을 int[][] 타입으로 변환하여 반환한다.
        int[][] answer = result.stream().toArray(int[][]::new);

        return answer;
    }

    public static void hanoi(int first, int center, int last, int N) {
        /**
         * 옮겨야 할 원판이 1개 남았다면 재귀를 종료한다.
         * 재귀 도중, 탑의 원판 이동여부를 result에 담는다.
         */
        if(N == 1) {
            result.add(new int[]{first, last});
            return;
        }else {
            hanoi(first, last, center, N-1);
            result.add(new int[]{first, last});
            hanoi(center, first, last, N-1);
        }        
    }

    public static void main(String[] args) {
        
        Solution sol = new Solution();
        int n = 2;        
        sol.solution(n);

    }

}

회고

-

---

출처

-

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.