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

문제 링크 : programmers.co.kr/learn/courses/30/lessons/60062

코딩테스트 연습 - 외벽 점검

문제 유형

Brute Force, DFS, 순열

 

[2020 카카오 블라인드 코딩 테스트]

weak의 크기가 15, dist의 크기가 8로 매우 작기 때문에 완전 탐색으로 접근할 수 있는 문제이다.

우선 각 친구들은 반드시 취약 지점에서 출발하는 것이 유리함은 자명하다. 같은 거리를 이동하더라도 반드시 최대의 취약 지점을 지나기 때문이다. (따라서 문제의 4.5 ~ 6.5 이동은 사실상 의미 없는 문구라 보면 된다.)

또한, 반시계 방향으로 이동 가능하다는 점도 무시할 수 있다. 항상 시계 방향으로 이동한다고 가정하여 문제를 풀어보자.

이 풀이에서는 모든 취약 지점에서 모든 친구들이 출발하는 경우를 탐색한다. 친구들이 배정되는 순서(즉, 순열) 및 어떤 취약점들이 점검되었는지는 Bitmask를 통해 구현하였으며,

모든 취약 지점을 점검한 상태(코드의 full_weak)에 도달했을 때 정답을 최솟값으로 갱신해 주면 된다.

 

[코드]

#include <string>
#include <vector>
#include <algorithm>
#include <memory.h>
 
using namespace std;
typedef pair<int, int> p;
typedef pair<int, p> pp;
 
vector<int> dist_list;
int full_weak, full_dist, N;
int weakpoint[200];
int ans = 99999999;
 
int get_num(int dstate){
    int ret = 0;
    for(int i = 0; i < dist_list.size(); i++) if(dstate & (1 << i)) ret++;
    return ret;
}
 
void dfs(int start, int end, int cur_dist, int wstate, int dstate){
    //curdist 만큼 범위를 cover
    int cur = end;
    if(weakpoint[cur] != -1) wstate |= 1 << weakpoint[cur];
    
    for(int i = 0; i < dist_list[cur_dist]; i++){
        cur++;
        if(cur == N) cur = 0;       //0지점에 도달
        if(cur == start) break;     //최초 출발 지점에 도달(종료)
        if(weakpoint[cur] != -1) wstate |= 1 << weakpoint[cur];
    }
    
    if(wstate == full_weak){
        //모든 취약점을 점검함
        ans = min(ans, get_num(dstate));
        return;
    }
    
    //다음 weakpoint부터 배치
    cur += 1; if(cur == N) cur = 0;
    while(weakpoint[cur] == -1) {
        cur++; 
        if(cur == N) cur = 0;
    }
    
    for(int i = 0; i < dist_list.size(); i++){
        if(dstate & (1 << i)) continue;     //이미 배치된 인원
        dfs(start, cur, i, wstate, dstate | (1 << i));
    }
    
}
 
int solution(int n, vector<int> weak, vector<int> dist) {
    dist_list = dist; N = n;        //global
    
    full_weak = (1 << weak.size()) - 1;
    full_dist = (1 << dist.size()) - 1;
    
    memset(weakpoint, -1, sizeof(weakpoint));
    for(int i = 0; i < weak.size(); i++) weakpoint[weak[i]] = i;
    
    for(int i = 0; i < weak.size(); i++){
        for(int j = 0; j < dist.size(); j++){
            dfs(weak[i], weak[i], j, 0, 1 << j); 
        }
    }
    
    if(ans == 99999999) return -1;    
    return ans;
}