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

DFS(or permutation)와 백트래킹을 이용해 모든 경우의 수를 탐색했다.

weak의 처음부터 끝까지 반복문을 순회하는데, 
각 반복마다 해당 weak의 위치부터 dist 거리만큼 검사한다.
검사하면서 weak의 위치면서, 아직 방문하지 않았다면 방문 표시를 하고 
백트래킹 기법으로 방문 표시를 다시 제거하기위해 store 배열에 저장한다.
다음 dist를 검사하기 위해 search_result 함수를 호출한다.
마지막으로 현재 반복문에서 store에 visited 위치를 알려주는 변수를 추출해 방문표시를 제거한다.
위의 순서를 반복하면 답을 찾을 수 있다.

#include <string>
#include <vector>
#include <climits>
#include <algorithm>
 
using namespace std;
 
bool visited[250];
bool weak_arr[250];
vector<int> store;
int answer = INT_MAX;
 
void serch_result(int count, int weak_count, int cur_dist, 
                  int n, vector<int> &weak, vector<int> &dist) {
    if (weak_count >= weak.size()) {
        answer = answer > count ? count : answer;
        return;
    }
    if (count > weak.size() || count >= answer || cur_dist < 0) { return; }
    for (int val: weak) {
        if (visited[val]) { continue; }
        int weak_count_temp = weak_count;
        int index = val - 1;
        while(++index - val <= dist[cur_dist]) {
            if (!visited[index % n] && weak_arr[index % n]) { 
                weak_count_temp++;
                store.push_back(index % n);
                visited[index % n] = true;
            }
        }
        
        serch_result(count + 1, weak_count_temp, cur_dist - 1, n, weak, dist);  
            
        while ((weak_count_temp--) - weak_count) {
            visited[store.back()] = false;
            store.pop_back();
        }
    }
}
 
int solution(int n, vector<int> weak, vector<int> dist) {
    sort(dist.begin(), dist.end());
    fill(visited, visited + 250, false);
    fill(weak_arr, weak_arr + 250, false);
    for (int i: weak) {
        weak_arr[i] = true;
    }
    
    serch_result(0, 0, dist.size() - 1, n, weak, dist);
    
    if(answer > weak.size()) { return -1; }
    return answer;
}

 

 

약간 다른 방법

#include <string>
#include <vector>
#include <climits>
#include <algorithm>
 
using namespace std;
 
bool visited[250];
bool weak_arr[250];
vector<int> store;
int answer = INT_MAX;
 
void serch_result(int count, int weak_count, int cur_dist, 
                  int n, vector<int> &weak, vector<int> &dist) {
    if (weak_count >= weak.size()) {
        answer = answer > count ? count : answer;
        return;
    }
    if (count > weak.size() || count >= answer || cur_dist < 0) { return; }
    
    for(int i = 0; i < weak.size(); i++) {
        if (visited[i]) { continue; }
        int weak_count_temp = weak_count;
        int count_check = 0;
        for (int j = 0; j < weak.size(); j++) {
            if (visited[j]) { continue; }
            int val = weak[j] - weak[i];
            if (val < 0) { val += n; }
            if (val <= dist[cur_dist]) {
                visited[j] = true;
                count_check++;
                weak_count_temp++;
                store.push_back(j);
            }
        }
        
        
        serch_result(count + 1, weak_count_temp, cur_dist - 1, n, weak, dist);  
        
        while(count_check--) {
            visited[store.back()] = false;
            store.pop_back();
        }
    }
}
 
int solution(int n, vector<int> weak, vector<int> dist) {
    sort(dist.begin(), dist.end());
    fill(visited, visited + 15, false);
    fill(weak_arr, weak_arr + 15, false);
    for (int i: weak) {
        weak_arr[i] = true;
    }
    
    serch_result(0, 0, dist.size() - 1, n, weak, dist);
    
    if(answer > weak.size()) { return -1; }
    return answer;
}