Java - [프로그래머스]60062 - 외벽 점검

출처

https://school.programmers.co.kr/learn/courses/30/lessons/60062

프로그래머스

 

문제

 

이 문제는 원형 모양의 레스토랑의 취약점을 점검 할때, 친구가 한시간동안 이동할 수 있는 거리는 각각 다르고 이 친구들을 적절히 보내 모든 취약점을 할 때 보내야 하는 친구의 최솟값을 구하는 문제이다. 만약 모두 점검할 수 없다면, -1을 리턴한다.

풀이

뭔가 처음부터 많이 헤맸던 문제이다. 단순히 취약점의 순열을 구하여 거리가 높은 친구를 순서대로 배치하는 방법을 생각했는데, 반례가 중간에 떠올라 처음부터 다시 풀게 되었던 문제이다. 결국 오래 고민하다가 힌트를 참고하여 해결할 수 있었던 문제이다.

 

이 문제를 해결하기 위한 핵심 개념은 완전 탐색, 순열 이다. 어떤 지점부터 어떤 친구를 먼저 보내야 할지 모르기 때문에 완전 탐색을 해 보고 그 뒤 최솟값을 구해야 한다.

 

1. 모든 weak의 경우를 만들기

우리는 취약점을 탐색할 경우의 수를 만들어야 한다. 다만 이 문제는 일반적인 직선 문제와 다르게, 원형이라는 점을 감안해야 한다. 원형이기 때문에 직선으로 펼쳐 [1, 5, 6, 10, 13, 17, 18, 22]와 같이 만들 수 있다. 예제와 같이 [1,5,6,10]의 weak이 존재한다면, weak에서 나올 수 있는 모든 케이스는 시작점을 순서대로 앞으로 옮겨다니며 [1,5,6,10], [5,6,10,13], [6,10,13,17], [10,13,17,18] 이 된다. 원형이기 때문에 시작점만 바꿔 돌면서 모든 경우를 탐색할 수 있다.

 

weak의 길이가 최대 15이므로, 이런식으로 모든 테스트 케이스를 만들어줘도 최대 15개까지밖에 되지 않기 때문에, 이 방법으로 모든 테스트 케이스를 만들어주면, 한방향으로만 탐색을 계속 진행해도 모든 경우를 다 탐색할 수 있다.

 

2. 모든 dist의 경우를 만들기

이 경우 누가 먼저 출발할지 모르기 때문에 완전탐색으로 문제를 해결한다. 순서 상관없이 순열을 dfs로 만들어 해결하였다.

3. 모든 weak 경우에 따라 모든 dist로 탐색을 진행

모든 weak에 맞춰 모든 dist의 경우를 검사한다. 특정 시작점에서 시작한 weak을, dfs로 만든 dist에 대해 check 함수를 호출해 몇명을 이용해 취약점을 탐색할 수 있는지 구한다.

 

만약 weak이 [1, 5, 6, 10] 이고 dist가 [7, 3, 5]라면 7인 친구를 이용해 먼저 1+7 = 8 이내의 1, 5, 6을 체크한다. 그 다음 취약점인 10 보다 첫번째 친구가 도달할 수 있는 거리가 작기때문에, 그다음 이동거리가 3인 친구를 이용하여 8 + 3 = 11 이내인 10을 체크하여 총 2명으로 탐색을 완료할 수 있다. for문과 현재의 posistion인 8, 11을 이용해 체크하도록 하였다. 만약 최종 position이 weak의 마지막에 미치지 못했다면 탐색을 완료하지 못했다는 뜻임으로, 최대값을 리턴하도록 구성하였다.

코드

import java.util.*;

class pgs60062 {

    int[] weak_circle, dist;
    int n, answer;

    public int solution(int n, int[] weak, int[] dist) {
        weak_circle = new int[weak.length * 2];
        answer = Integer.MAX_VALUE;
        this.dist = dist;
        this.n = n;

        for (int i = 0; i < weak.length; i++) {
            weak_circle[i] = weak[i];
            weak_circle[i + weak.length] = weak[i] + n;
        }

        for (int i = 0; i < weak.length; i++) {
            makeDistCase(i, 0, new boolean[dist.length], new int[dist.length]);
        }

        return answer == Integer.MAX_VALUE ? -1 : answer;
    }

    public void makeDistCase(int start, int depth, boolean[] visited, int[] permutation) {
        if (depth == dist.length) {
            answer = Math.min(check(start, permutation), answer);
            return;
        }

        for (int i = 0; i < permutation.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                permutation[depth] = dist[i];
                makeDistCase(start, depth + 1, visited, permutation);
                visited[i] = false;
            }
        }
    }

    public int check(int start, int[] permutation) {
        int person = 1;
        int pos = weak_circle[start] + permutation[person-1];
        for (int i = start; i < start + weak_circle.length/2; i++) {
            if (pos < weak_circle[i]) {
                person++;
                if (person > permutation.length) {
                    return Integer.MAX_VALUE;
                }
                pos = weak_circle[i] + permutation[person - 1];
            }
        }
        return person;
    }


}