외벽 점검 [자바]

 

🧫 문제 분석

✔️ 출처

외벽 점검 level 3

📖 문제

 

DFS로 풀려다가 for문으로 그리디하게 풀 수 있을것 같아 바꿔풀었다.

 

각 취약지점을 기준으로 시계방향으로 출발했을 때 걸리는 시간의 누적합을 구한다.

 예시로 들자면

1	5	6	10
0	4	5	9
8	0	1	5
7	11	0	4
3	7	8	0

 

그 다음 for문으로 각 weak을 순회하면서 각 지점을 순차적으로 출발지점으로 정한다.

 

최소한의 인원으로 처리해야하므로 가장 많이 처리할 수 있는 친구부터 출발지점에서 처리할 수 있는 취약지점을 탐색한다.

가장 많이 처리할 수 있는 친구는 문제에서 입력으로 dist에 오름차순으로 주어진다.

 

여기서 예시로는 마지막 친구가 4의 거리를 처리하고 현재 출발지점이 1 이므로, 5까지 처리가 가능하다. 

 

구했다면 이제 해당 취약지점을 더 적은 이동거리를 갖는 친구가 처리가능한지 탐색한다.

 

예를 들어 출발지점이 5이고, 이동거리 4를 갖는 친구가 처리할 수 있는 취약지점은 5~6까지이다. 

하지만 거리 3의 손해를 본다. 따라서 더 적은 친구로 커버가 가능한지 탐색하는 것이다. 여기서는 1의 이동거리를 갖는 친구로 대체 가능하다.

 

이렇게 그리디하게 풀어나가면 된다. 

 

---

🔅 문제 풀이

import java.util.*;


class Solution {
    static int[][] arr;
    static int weakLen;

    // 전부 점검할 수 없는 경우에는 -1
    public int solution(int n, int[] weak, int[] dist) {
        int answer = Integer.MAX_VALUE;
        weakLen = weak.length;
        
        arr = new int[weakLen][weakLen];
        
        // 각 취약지점을 출발점으로 정했을때 거리 누적합
        for (int i = 0; i < weakLen; i++) {
            for (int j = 0; j < weakLen; j++) {
                int idx = (i + j) % weakLen;
                
                if (j == 0) {
                    arr[i][idx] = 0;
                }else {
                    int prev = (idx - 1 + weakLen) % weakLen;
                    if (idx == 0) {
                        arr[i][idx] = (weak[idx] - weak[prev] + n ) % n + arr[i][prev];
                    } else {
                        arr[i][idx] = (Math.abs(weak[prev] - weak[idx]) % n) + arr[i][prev];
                    }
                }
            }
            
            System.out.println(Arrays.toString(arr[i]));
        }
        
        
        for (int i = 0; i < weakLen; i++) {
            boolean[] visited = new boolean[weakLen];
            boolean[] isMoved = new boolean[dist.length];
            
            int cnt = 0; // 현재를 출발지점으로 했을때 처리한 취약지점 개수 
            int idx = i; // 현재 선택된 취약지점 
            int select = i; // 다음 취약지점을 출발지로 지정하는 인덱스 
            int friend = dist.length - 1;
            int friendCnt = 0;
            
            while (cnt < weakLen) {
                boolean friendCheck = false;
            
                // 이동거리가 큰 친구중 아직 일하지 않은 사람 선택
                for (int j = dist.length - 1; j >= 0; j--) {
                    if (!isMoved[j]) {
                        friend = j;
                        friendCheck = true;
                        break;
                    }
                }
                
                // 모든 친구들이 일했다면 정지 
                if (!friendCheck) {
                    if (cnt != weakLen) {
                        friendCnt = Integer.MAX_VALUE;
                    }
                    break;
                }
                
                friendCnt++; // 사용된 친구 수 + 1     
                cnt++; // 처음 위치도 카운팅
                visited[idx] = true; // 처음 위치 바로 방문
                
                // 현재 친구가 얼만큼 커버가 가능한지 
                while (true) {
                    if (cnt == weakLen) break;
                    
                    if (arr[select][(idx + 1) % weakLen] <= dist[friend]) {
                        idx = (idx + 1) % weakLen;
                        visited[idx] = true;
                        cnt++;
                    } else {
                        break;
                    }
                }
                
                // 더 작은 이동거리를 갖는 친구가 현 위치에서 최대이동이 가능한지 
                for (int j = friend; j >= 0; j--) {
                    if (!isMoved[j] && arr[i][idx] <= dist[j]) {
                        friend = j;
                    } 
                }
                
                isMoved[friend] = true;
                idx = (idx + 1) % weakLen;
                select = idx;
            }
            
            answer = Math.min(answer, friendCnt);
        }
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
}

 

 

 

DFS 풀이보다 훨씬 빠르다.

 

🔅 리팩토링

❗ 오답노트 / 필요한 지식

1. DFS로 처음 시도하다가 시간초과나서 생각을 바꿔서 풀었는데 좋은 방향인 것 같다.