프로그래머스 외벽 점검

문제

레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 도중에 주기적으로 외벽의 상태를 점검해야 할 필요가 있습니다.

레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 n미터이며, 외벽의 몇몇 지점은 추위가 심할 경우 손상될 수도 있는 취약한 지점들이 있습니다. 따라서 내부 공사 도중에도 외벽의 취약 지점들이 손상되지 않았는 지, 주기적으로 친구들을 보내서 점검을 하기로 했습니다. 다만, 빠른 공사 진행을 위해 점검 시간을 1시간으로 제한했습니다. 친구들이 1시간 동안 이동할 수 있는 거리는 제각각이기 때문에, 최소한의 친구들을 투입해 취약 지점을 점검하고 나머지 친구들은 내부 공사를 돕도록 하려고 합니다. 편의 상 레스토랑의 정북 방향 지점을 0으로 나타내며, 취약 지점의 위치는 정북 방향 지점으로부터 시계 방향으로 떨어진 거리로 나타냅니다. 또, 친구들은 출발 지점부터 시계, 혹은 반시계 방향으로 외벽을 따라서만 이동합니다.

외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어질 때, 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최소값을 return 하도록 solution 함수를 완성해주세요.

코드

import java.util.*;
import java.util.stream.*;

class Solution {
    /**
    이동거리가 긴 사람부터 투입하는 것이 무조건 이득
    아직 방문안한 모든 노드에서 시작해서 최대한 이동하도록 할 거임
    모든 노드에서 시작하므로 시계, 반시계 방향은 구별할 필요가 없음
    **/
    public int solution(int n, int[] weak, int[] dist) {
        //내림차순으로 이동 가능 거리 정렬
        dist=Arrays.stream(dist)
            .boxed()
            .sorted((o1, o2)->{
                return o2-o1;
            })
            .mapToInt(o->o)
            .toArray();
        
        //정답 출력
        int answer=recovery(new boolean[weak.length], 0, dist, weak, 0, n);
        return answer==Integer.MAX_VALUE? -1: answer;
    }
    
    //핵심 로직
    public static int recovery(boolean[] visited, int start, int[] friends, int[] weak, int index, int n){
        //모두 방문했으면 현재의 index(사용된 사람의 수) 리턴
        if(check(visited))
            return index;
        //모두 방문은 못했지만 남은 사람이 없으면 불가능
        if(index==friends.length)
            return Integer.MAX_VALUE;
        
        //현재 사람의 최대 이동 거리
        int maxDistance=friends[index];
        //리턴할 결과 변수 answer, 현재 사람의 현재 상황에서 최대로 방문한 노드 갯수 previous
        //previous는 불필요한 DFS 탐색을 줄이기 위함
        int answer=Integer.MAX_VALUE;
        int previous=0;
        
        //모든 노드에 대해서
        for(int i=0; i<weak.length; i++){
            //다음 방문할 인덱스(배열의 끝이 넘어가면 0이 되도록)
            int nextIndex=(start+i)%weak.length;
            
            //이미 방문한 곳이면 continue
            if(visited[nextIndex])
                continue;
            
            //nextIndex 노드를 시작점으로 했을 때 방문 가능한 노드를 저장할 update Set
            Set<Integer> update=new HashSet<>();
            //어디까지 방문할 수 있는지 현재의 노드에서 증가시키기 위한 인덱스
            int end=nextIndex-1;
            
            //모든 노드에 대해서
            for(int j=0; j<weak.length; j++){
                //현재 노드부터 시작
                end=(end+1)%weak.length;
                
                //방문했으면 continue
                if(visited[end])
                    continue;
                
                //현재의 노드에서 end 노드까지의 거리가 최대 이동 가능 거리 이하라면 update에 추가
                //더이상 불가능하면 break
                if((n+weak[end]-weak[nextIndex])%n<=maxDistance)
                    update.add(end);
                else
                    break;
            }
            
            /**
            현재 사람이, 
            다른 시작점에서 갔던 최대 노드 갯수 > 현재의 시작점에서 최대 노드 갯수
            라면 재귀 호출할 필요가 없음
            **/
            if(previous>update.size())
                continue;
            else
                previous=update.size();
            
            //방문 표시
            update.forEach(o->visited[o]=true);
            
            //다음 깊이(index+1) 탐색
            answer=Math.min(answer, 
                            recovery(visited, end, friends, weak, index+1, n));

            //방문 표시 취소
            update.forEach(o->visited[o]=false);
        }
        
        return answer;
    }
    
    //모두 방문했는 지 여부 리턴
    public static boolean check(boolean[] visited){
        for(boolean b:visited)
            if(!b)
                return false;
        
        return true;
    }
}

해결 과정

1. 우선 무조건 이동거리가 긴 사람부터 투입하는 것이 항상 최적이라고 생각했다. 따라서 내림차순 정렬한 뒤에 시작.

   모든 노드에서 시계 방향, 반시계 방향으로 최대한 이동했을 때 최대로 방문하는 시작 노드와 방향으로 방문한 뒤, 다음 사람 투입.

2. 당연하지만 반례가 있다. 최대 방문 횟수가 똑같은 경우가 2가지 이상일 경우, 둘다 탐색해봐야 한다. 그래서

   최대 방문횟수가 같을 경우, 이동 거리가 긴 경우를 선택해서 방문한 뒤, 다음 사람 투입.

3. 오히려 이동 거리가 작을 때가 최적일 수도 있다. 다음 방법으로는

   모든 노드를 출발점으로 했을 때 모든 경우에 대해서 DFS.
   1번 사람이 0번 노드에서 출발했을 때, 1번 노드에서 출발했을 때, ...
   다른 사람도 마찬가지

4. 정답은 다 맞지만 시간 초과 발생.

   불필요한 탐색을 줄이기 위해서 모든 노드를 출발점으로 탐색할 때, 이전보다 적은 수의 노드를 방문하는 경우는 탐색할 필요가 없다.
   1번 사람이 0번 노드에서 출발했을 때 2개의 노드를 방문할 수 있고,
   1번 노드에서 출발했을 때 최대 1개의 노드를 방문할 수 있다면,
   굳이 1번 노드에서 출발하는 경우는 탐색할 필요가 없다.

5. 😁(카카오 개어렵다;)