[PG] 외벽 점검 [C++]

 

프로그래머스

 

해결하는데 좀 오래 걸렸다.

처음에는 구현, 그리디 방식으로 해결이 가능할 것 같다고 생각했지만 실패했다.

1. 원형으로 이루어진 외벽을 일직선으로 편 후, 길이를 2배 늘린다.

2. 점검할 수 있는 거리를 내림차순으로 정렬.

3. 각 친구가 점검할 수 있는 만큼 최대한의 취약 지점을 찾아 처리.

이런 방식으로 가능할 것이라 생각했지만,

'점검 거리 내에 포함되는 취약 지점의 수가 같은 경우가 2개 이상 생기면 어떤 구간을 선택해야 하는가'를

해결할 수 없어서 다른 방법을 고민했다.

 

결론적으로 백트래킹을 써서 해결.

 

1. 취약 지점을 일직선으로 편 후, 길이를 2배 늘려준다.

2. 점검할 수 있는 거리를 내림차순으로 정렬.

3. 백트래킹 시작.

4. 아직 점검하지 않은 모든 취약 지점부터 자신이 점검할 수 있는 최대 거리까지 점검.

5. 점검 지점들을 확인했음을 표시 후, 다음 사람으로 넘어가 4번을 반복.

 

이 과정에서 함수 콜을 줄이기 위해, 현재까지 점검에 참여한 친구의 수가 지금까지 구한 답보다 많다면 return 하도록 했다.

 

 

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int answer = 101;
int weakSize = 0;
bool checked[31];
vector<int> weaks;
vector<int> dists;

void sol(int friendIndex, int checkedWeaks) {
    if (checkedWeaks == weakSize) {
        answer = min(answer, friendIndex);
        return;
    }
    if (friendIndex == dists.size() || friendIndex >= answer) {
        return;
    }
    
    for (int i = 0; i < weakSize; i++) {
        if (checked[i]) {
        	// 이미 확인된 곳이라면 pass
            continue;
        }
        
        // 자신이 점검할 수 있는 최대 끝 지점 찾기
        int endIndex = i;
        for (int j = i; j < weaks.size(); j++) {
            if (checked[j]) {
                break;
            }
            if (weaks[j] - weaks[i] > dists[friendIndex]) {
                break;
            } else {
                endIndex = j;
            }
        }
        
        // 점검 표시
        for (int k = i; k <= endIndex; k++) {
            checked[k] = true;
            if (k - weakSize >= 0) {
                checked[k - weakSize] = true;
            }
            if (k + weakSize < weaks.size()) {
                checked[k + weakSize] = true;
            }
        }
        
        // 다음 사람으로 점검 수행
        sol(friendIndex + 1, checkedWeaks + endIndex - i + 1);
        
        // 점검 표시 해제
        for (int k = i; k <= endIndex; k++) {
            checked[k] = false;
            if (k - weakSize >= 0) {
                checked[k - weakSize] = false;
            }
            if (k + weakSize < weaks.size()) {
                checked[k + weakSize] = false;
            }
        }
    }
}

int solution(int n, vector<int> weak, vector<int> dist) {
    weaks = weak;
    dists = dist;
    sort(dists.begin(), dists.end(), greater<int>());
    
    weakSize = weak.size();
    for (int i = 0; i < weakSize; i++) {
        weaks.push_back(weak[i] + n);
    }
    
    sol(0, 0);
    
    if (answer == 101) {
        answer = -1;
    }
    
    return answer;
}