문제 링크 : programmers.co.kr/learn/courses/30/lessons/60062
문제 유형
Brute Force, DFS, 순열
[2020 카카오 블라인드 코딩 테스트]
weak의 크기가 15, dist의 크기가 8로 매우 작기 때문에 완전 탐색으로 접근할 수 있는 문제이다.
우선 각 친구들은 반드시 취약 지점에서 출발하는 것이 유리함은 자명하다. 같은 거리를 이동하더라도 반드시 최대의 취약 지점을 지나기 때문이다. (따라서 문제의 4.5 ~ 6.5 이동은 사실상 의미 없는 문구라 보면 된다.)
또한, 반시계 방향으로 이동 가능하다는 점도 무시할 수 있다. 항상 시계 방향으로 이동한다고 가정하여 문제를 풀어보자.
이 풀이에서는 모든 취약 지점에서 모든 친구들이 출발하는 경우를 탐색한다. 친구들이 배정되는 순서(즉, 순열) 및 어떤 취약점들이 점검되었는지는 Bitmask를 통해 구현하였으며,
모든 취약 지점을 점검한 상태(코드의 full_weak)에 도달했을 때 정답을 최솟값으로 갱신해 주면 된다.
[코드]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
#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;
}
|
cs |
'알고리즘 > 프로그래머스 문제풀이' 카테고리의 다른 글
[프로그래머스] 뉴스 클러스터링 (0) | 2021.03.08 |
---|---|
[프로그래머스] 추석 트래픽 (0) | 2021.03.08 |
[프로그래머스] 자물쇠와 열쇠 (0) | 2021.02.17 |
[프로그래머스] 매출 하락 최소화 (0) | 2021.02.14 |
[프로그래머스] 카드 짝 맞추기 (0) | 2021.02.14 |