프로그래머스 외벽 점검

프로그래머스 외벽 점검

문제를 읽고 나서 떠오른 풀이법은 그리디 + 완전탐색이었다. 그리디로 생각한 이유는 다음과 같다.

• 취약 지점 점검 시, 출발점은 항상 취약 지점이어야 한다.
• 점검에 투입된 친구를 최소화 해야하니 이동 거리가 높은 친구를 먼저 투입한다.

그래서 항상 이동 거리가 높은 친구가 먼저 출발하고, 모든 취약 지점을 출발점으로 하는 경우를 전부 탐색해 문제를 해결하려 했으나, 채점 결과 오답이 나왔다. 반례를 찾아보니 다음과 같았다.

n = 16
weak = [1,2,3,4,5,7,8,10,11,12,14,15]
dist = [1,1,2,4]

1번 지점을 시작으로 4, 1, 2, 1 순서로 친구가 출발해야 모든 지점을 점검할 수 있고, 정답은 4이지만, 나의 풀이로는 4, 2, 1, 1 순서로 친구가 출발해 -1을 반환하는 것을 발견했다. "이동 거리가 높은 친구가 먼저 출발한다"는 잘못된 기준이었다.

그래서 백트래킹 알고리즘으로 모든 경우를 탐색하도록 코드를 수정했다.

수정된 코드

class Solution {
    static int minValue = Integer.MAX_VALUE;
    static boolean[] visited;
    static int n2; //외벽의 둘레

    public static int solution(int n, int[] weak, int[] dist) {
        visited = new boolean[dist.length];
        n2 = n;
        for (int i = 0; i < weak.length; i++) {
            dfs(i, weak, dist, 0, 0);
        }
        return minValue == Integer.MAX_VALUE ? -1 : minValue;
    }

    static void dfs(int index, int[] weak, int[] dist, int clearCount, int friendCount) {
        if (clearCount == weak.length) {
            minValue = Math.min(minValue, friendCount);
        }
        for (int i = 0; i < dist.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                friendCount++; //점검에 투입된 친구 수
                int distance = dist[i];
                while (distance >= 0) {
                    if (index == weak.length - 1) { //외벽 사이의 거리를 반시계방향으로 계산해야되는 경우,
                        int current = weak[index];
                        int next = weak[0];
                        distance -= (n2 + next) - current;
                    } else {
                        int current = weak[index];
                        int next = weak[index + 1];
                        distance -= next - current;
                    }
                    index = (index + 1) % weak.length; //점검해야 할 지점 index
                    clearCount++; //점검이 완료된 외벽 수
                    if (clearCount == weak.length) {
                        break;
                    }
                }
                dfs(index, weak, dist, clearCount, friendCount);
                visited[i] = false;
            }
        }
    }
}

올바르게 작성한 것 같았지만, 테스트 결과 오답이 나왔고, 어떤 부분이 잘못되었는지 디버깅하는 데 어려움을 겪었다. 문제는 각 단계에서 메서드 매개변수 (index, clearCount, friendCount)를 따로 저장해 넘기는 것이 아니라, 연산된 값을 바로 다음 단계로 넘겨 잘못된 값들이 재귀적으로 전달되는 것이었다.

쉽게 설명하자면,

1번 친구 - 2번 친구 - 3번 친구 - 탐색 완료 후,
1번 친구 - 3번 친구 - 4번 친구 ... 순으로 탐색이 이루어질 때,
2번 친구가 점검한 외벽 수, 2번 친구가 포함된 친구 수가 다음 메서드로 전달되어 올바르게 동작하지 않음을 알아냈다.

다시 수정한 코드

class Solution {
    static int n2;
    static int min = Integer.MAX_VALUE;
    static boolean[] visited;

    public static int solution(int n, int[] weak, int[] dist) {
        n2 = n;
        visited = new boolean[dist.length];
        for (int i = 0; i < weak.length; i++) {
            dfs(weak, dist, i, 0, 0);
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }

    static void dfs(int[] weak, int[] dist, int index, int clearCount, int friendCount) {
        if (clearCount == weak.length || friendCount >= min) { //점검에 참여한 친구 수가 최소값 보다 작으면 탐색 중단.
            min = Math.min(min, friendCount);
            return;
        }
        for (int i = 0; i < dist.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                int newClearCount = clearCount;
                int newFriendCount = friendCount;
                int newIndex = index;
                newFriendCount++;
                int distance = dist[i];
                while (distance >= 0) {
                    if (newIndex == weak.length - 1) {
                        int current = weak[newIndex];
                        int next = weak[0];
                        distance -= (n2 + next - current);
                    } else {
                        int current = weak[newIndex];
                        int next = weak[newIndex + 1];
                        distance -= (next - current);
                    }
                    newIndex = (newIndex + 1) % weak.length;
                    newClearCount++;
                    if (newClearCount == weak.length) {
                        break;
                    }
                }
                dfs(weak, dist, newIndex, newClearCount, newFriendCount);
                visited[i] = false;
            }
        }
    }
}

재귀적으로 메서드를 실행할 때, 변수를 새로 저장하고 연산해 넘겨주는 방식으로 변경했으며, 추가로 불필요한 탐색을 막기 위해 friendCount가
min 보다 크거나 같다면 탐색을 중단하도록 수정하였다.