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

문제 링크

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

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

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. dfs 기반 재귀호출을 통해 n개의 원판 문제를 줄여 나간다.

 해당 문제는 n개의 원판 문제를 어떻게 쪼개서 해결할 수 있는 지가 중점인 문제이다. 흔히 이런 문제의 경우 총 움직인 횟수 등을 물어보는데, 이 문제의 경우는 과정 자체를 답으로 요구하기 때문에 n개의 원판을 쪼개며 이들이 어떻게 움직여야 하는 지를 재귀호출에서 지정해주어야 한다.

 문제에서 요구하는 바는 주어진 n개의 원판을 위치 1에서 3으로 이동해야 함을 명시하는 데, 이런 경우 크게 3가지 과정으로 쪼개면 이렇게 표현이 가능하다.

 

• n - 1개의 원판을 위치 1에서 2로 옮긴다.
• 남은 가장 큰 한 개의 원판을 위치 1에서 3으로 옮긴다.
• 다시 위치 2의 원판 n - 1개를 위치 3으로 옮긴다.

  이 경우 이제 위치 1, 2, 3을 임의의 위치 A, B, C로 대체하면 좀 더 일반화된 문제로 쪼갤 수 있다. 앞선 과정에서 첫 번째 부분 문제인 n - 1개를 위치 1에서 2로 옮기는 문제도, n - 2개 원판들을 1 -> 3으로, 남은 한 개를 1 -> 2로, 다시 n - 2개 원판들을 3 -> 2로 옮기는 문제로 쪼갤 수 있다.

 결국 재귀호출을 통해 문제를 해결하는 함수를 작성한 다음, 해당 함수를 실행하면 문제의 과정을 구할 수 있다. 또한 이러한 과정을 순서대로 어느 곳에 저장해두어야 하기 때문에, 큐를 생성해 함수의 과정을 그때그때 push한 다음 문제가 끝나면 한 번에 답안 배열에 옮겨 적는 방식으로 과정을 모두 저장했다.

 

class Solution {
    Queue<Infor> q = new LinkedList<>();//dfs 탐색의 결과가 저장될 큐
    int[][] midpoint = {{0, 0, 0, 0}, {0, 0, 3, 2}, {0, 3, 0, 1}, {0, 2, 1, 0}}; //남은 위치 찾기용 배열

    public int[][] solution(int n) {
        int[][] answer = new int[((int) Math.pow(2, n)) - 1][2];//답안 배열 초기화
        int index = 0;

        move(n, 1, 3); //n개 원판의 위치 1에서 3으로 이동

        while (!q.isEmpty()) {//결과가 담긴 큐를 비우며 answer 배열 채우기
            Infor infor = q.poll();
            answer[index][0] = infor.from;
            answer[index][1] = infor.to;

            ++index;
        }

        return answer;
    }

    void move(int roundPlateCount, int from, int to) {//재귀호출
        if (roundPlateCount == 1) { //기저 조건
            q.add(new Infor(from, to));
            return;
        }

        move(roundPlateCount - 1, from, midpoint[from][to]);
        move(1, from, to);
        move(roundPlateCount - 1, midpoint[from][to], to);
    }

    class Infor{//원판 한 개의 과정이 담기는 클래스
        int from, to;

        public Infor(int from, int to) {
            this.from = from;
            this.to = to;
        }
    }
}

결과