[완전탐색] 외벽 점검 - 2020 KAKAO BLIND RECRUITMENT

기존에 필자가 풀이한 방법은 통과는 했지만 실행 시간이 꽤 길어서 다른 좋은 풀이 방법을 찾아보았다. 참고한 풀이 방법의 출처는 맨 아래에 표시하겠다.

 

해결 방법

필자가 설명할 풀이 방법은 완전 탐색을 사용한 방법이다.

이런 식으로 원을 탐색하는 문제는 2n 크기의 1차원 배열로 풀어서 생각하면 쉽다. 늘어난 부분은 원의 위치 0을 기준으로 2바퀴 째 도는 부분인 것이다. 즉, weak 배열의 크기를 2배로 늘리고 늘어난 부분은 기존의 원소에 n을 더해서 추가하면 된다.

※ 예) n=12이고 weak=[1, 5, 6, 10]인 경우에는 weak=[1, 5, 6, 10, 13, 17, 18, 22]로 만든다. 

이렇게 되면 기존의 weak의 크기를 w라고 했을 때, [0, w) 범위의 정수인 임의의 i에 대하여 weak[i]~weak[i+w-1] 부분을 모두 점검할 수 있는 모든 경우들을 따져서, 점검한 친구 수의 최솟값을 구하면 된다.

또, 탐색은 항상 취약 지점부터 시작하도록 해서 탐색 시간을 줄인다.

그리고 친구들의 투입 순서는 자유이기 때문에 순열을 이용해서 투입 순서에 따른 모든 경우의 수를 따져주면 된다.

 

 

소스 코드

#include <vector>
#include <algorithm>
using namespace std;

int solution(int n, vector<int> weak, vector<int> dist) {
    int answer = 9;
    
    int wsize = weak.size();
    weak.resize(2*wsize);
    for(int i=wsize;i<weak.size();i++) weak[i] = weak[i-wsize]+n;

    sort(dist.begin(),dist.end());

    do{
        for(int i=0;i<wsize;i++){
            int start = weak[i]; // 탐색 시작 위치
            int end = weak[i+wsize-1]; // 탐색 종료 위치
            for(int j=0;j<dist.size();j++){ // dist 배열에 있는 친구들을 순서대로 투입
                start += dist[j];
                if(start >= end){
                    answer = min(answer,j+1);
                    break;
                }
                
                // next : 마지막으로 닦은 외벽 이후의 최초 weak 지점
                int next=weak[weak.size()-1];
                for(int j=0;j<weak.size();j++) {
                    if(weak[j]>start) {
                        next=j;
                        break;
                    }
                }
                start = weak[next]; // next 지점을 시작 위치로 지정
            }
        }
    } while(next_permutation(dist.begin(),dist.end()));

    if(answer == 9) return -1;
    return answer;
}

 

테스트 케이스 25개 모두 정답

 

풀이 방법 참조 : https://yjyoon-dev.github.io/kakao/2021/01/04/kakao-wallcheck/

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/60062