[프로그래머스] 고고학 최고의 발견

프로그래머스

 

문제를 분할하는 방법은 문제 해결 방법의 절차를 쪼개는 방법과 문제의 범위를 쪼개는 방법이 있다는 것을 생각하게 해주는 문제였다.

여기에서는 문제의 범위를 쪼개서 생각하는 것이 중요한데 절차적으로 어떻게 해결하면 좋을지만 생각하니 문제 해결의 실마리를 놓치고 삽질을 하게된 원인인 것 같다고 생각한다.

 

해결 과정

완전 탐색으로 문제를 푼다고 가정하면 각 시계가 90도, 180도 270도 0도 회전하는 경우를 생각하고 그것이 연속적으로 n제곱 만큼 있다.

 

그래서 완전탐색으로 모든 경우를 탐색하게 되면 4의 n제곱 승의 계산이 최악의 경우 필요하기 때문에 알고리즘을 간단하게 만들어야 한다.

 

문제에서는 n의 크기가 겨우 8밖에 되지 않기 때문에 n의 크기 자체는 작다. 하지만 시간 복잡도가 무시무시하게 뻥튀기가 된다.

 

그래서 생각한 것은 4를 1로 바꿀 수 없을까? 였다.

 

만약 회전하는 각도를 1의 시간 복잡도 해결하면 제곱의 숫자가 무시막지하더라도 1이기 때문이다.

 

그러나 이러면 시간 복잡도가 n제곱으로 바뀌는데 이것은 너무 효율적이었다. 그래서 이상해서 아니라고 생각했다.

 

다음으로 생각한 것은 제곱하는 숫자를 줄일 수 없을까? 였다. 그러나 어떤 방법으로 줄여야할지 갈피가 잡히지 않아서 다른 사람들의 풀이를 좀 찾아보면 아이디어를 얻었다.

 

문제의 해결 아이디어는 첫번째 줄(row) 회전이 결정된 상태에서는 다음 번째 줄에서는 회전은 이전 줄의 요소에 영향을 받아 결정된다는 것이었다.

 

이것은 부분적으로 4번의 계산을 1번을 줄여주는 방법이었다.

 

그래서 처음 첫번째 줄의 회전을 결정해주는 이전 줄이 없기 때문에 첫번째 줄을 회전가능한 모든 조합의 수를 계산하고 이를 기반으로 다음 줄의 회전을 결정하여 그 결과를 판단해서 옳바르게 회전을 하였는지 그리고 최소한으로 회전을 하였는지 판단하면 되었다.

 

이 방법을 통해서 4의 n제곱의 제곱 시간 복잡도가 4의 n제곱가 줄어들 수 있었다.

 

첫번째 줄의 회전 방법은 dfs방식으로 가능한 조합을 만들고 이를 활용해서 퍼즐을 회전시키고 회전된 퍼즐이 잘 정렬이 되었다면 회전한데 소요된 행동을 갱신하면 되겠다는 생각을 했고 다음 코드로 구현했다.

 

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class Solution {

    int[][] originPuzzle;
    int answer = Integer.MAX_VALUE;

    public int solution(int[][] clockHands) {

        originPuzzle = clockHands;
        int[] rotationBuffer = new int[clockHands[0].length];
        dfs(rotationBuffer, 0, clockHands.length);

        return answer;
    }

    public int[][] clone(int[][] puzzle, int[] firstDirect) {
        int[][] clone = new int[puzzle.length + 1][puzzle[0].length];
        Arrays.setAll(clone[0], col -> firstDirect[col]);
        for (int i = 0; i < puzzle.length; i++) {
            int row = i;
            Arrays.setAll(clone[i+1], col -> puzzle[row][col]);
        }
        return clone;
    }

    public void dfs(int[] rotation, int depth, int n) {
        if (depth == n) {//한줄 회전 결정
            int[][] clone = clone(originPuzzle, rotation);
            int move = 0;
            //다음 줄 부터 이전 배열을 통해서 회전시킨다.
            move += rotationPuzzle(clone);
            //퍼즐이 정답인지 확인한다. 정답이면 사용한 회전 수를 갱신한다.
            if (isAligned(clone)) answer = Math.min(answer, move);
            return;
        }
        for (int degree = 0; degree < 4; degree++) {
            rotation[depth] = degree;
            dfs(rotation, depth + 1, n);
        }
    }

    public boolean isRange(int r, int c, int[][] puzzle) {
        return r >= 0 && r < puzzle.length && c >= 0 && c < puzzle[0].length;
    }

    int[][] next = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {0, 0}};

    public List<int[]> getNear(int r, int c, int[][] puzzle) {
        List<int[]> result = new LinkedList<>();
        for (int[] n : next) {
            int nr = r + n[0], nc = c + n[1];
            if (isRange(nr, nc, puzzle)) result.add(new int[]{nr, nc});
        }
        return result;
    }

    public void rotation(int r, int c, int degree, int[][] puzzle) {
        List<int[]> rotationIndexes = getNear(r, c, puzzle);
        for (int[] index : rotationIndexes) {
            int nr = index[0], nc = index[1];
            puzzle[nr][nc] = (puzzle[nr][nc] + degree) % 4;
        }
    }

    public int rotationPuzzle(int[][] puzzle) {
        int count = 0;
        for (int row = 1; row < puzzle.length; row++) {
            for (int col = 0; col < puzzle[0].length; col++) {
                //위 줄의 방향을 확인하고 회전 각도 결정
                int degree = (4 - puzzle[row - 1][col]) % 4;
                if (degree != 0) {
                    count += degree;
                    rotation(row, col, degree, puzzle);
                }
            }
        }
        System.out.println();
        return count;
    }

    public boolean isAligned(int[][] puzzle) {
        for (int[] row : puzzle)
            for (int component : row)
                if (component != 0) return false;
        return true;
    }
}