문제 링크
조건
- n : 외벽의 길이, 1~200 이하 자연수
- weak : 외벽의 취약지점 배열, 길이 1~15
- dist : 각 친구마다 1시간 동안 이동할 수 있는 거리, 길이 1~8
- 외벽의 모든 취약지점을 전부 점검하기 위해 최소로 필요한 친구 수 리턴, 불가능하면 -1 리턴
접근 방법
- dist배열 내림차순 정렬 => 1시간 동안 많이 이동할 수 있는 친구 순으로 정렬
- 친구마다 각 weak지점에서 출발할 때 점검할 수 있는 지점을 저장=>BitMask 활용
- 친구의 점검 범위를 미리 저장하지 않고 permutation(점검하러 갈 친구들의 점검 시작 위치 순열)을 구할 때마다 매번 점검 범위를 체크해주면 테스트케이스 1개 시간초과(13번)
- 점검에 필요한 친구 수를 1명부터 늘려가며 permutation 구함
- dist배열을 미리 내림차순 정렬 해놨기 때문에 맨 앞 친구부터 차례대로 선택
- permutation : 점검하러 갈 친구들의 점검 시작 위치 순열
- 순열을 구하면서 2번에서 저장해뒀던 정보로 점검 가능한 취약지점 합집합 구함 => BitMask 활용
솔루션
class Solution {
int weak_cnt;//취약지점 개수
int[][] fr;//친구가 각 취약지점에서 이동을 시작했을 때 점검 가능한 범위 체크
public int solution(int n, int[] weak, int[] dist) {
int answer = -1;
//dist 내림차순 정렬(1시간 동안 많이 움직일 수 있는 친구순)
for(int i = 0; i < dist.length-1; i++){
for(int j = i+1; j < dist.length; j++){
if(dist[i] < dist[j]){
int tmp = dist[i];
dist[i] = dist[j];
dist[j] = tmp;
}
}
}
weak_cnt = weak.length;
int peo = dist.length;
//친구마다 각 weak지점에서 출발해서 어느 지점까지 체크할 수 있는지 확인
fr = new int[peo][weak_cnt];
for(int i = 0; i < peo; i++){
int dis = dist[i];//i번째 친구가 1시간 동안 이동할 수 있는 거리
for(int j = 0; j < weak_cnt; j++){
int s = weak[j];//출발지점
for(int k = 0; k < weak_cnt; k++){
int cur = weak[k];
if(s + dis >= n){//외벽 크기를 넘어가는 경우
if(cur >= s || cur <= s+dis - n) fr[i][j] |= (1 << k);//도달할 수 있는 지점 저장
}else{
if(cur >= s && cur <= s+dis) fr[i][j] |= (1 << k);
}
}
}
}
//점검 나갈 친구 시작 위치 permutation
for(int i = 1; i < peo+1; i++){
if(permu(0,0,0,i)){
answer = i;
break;
}
}
return answer;
}
/**
flag : 선택된 start_point(취약지점) 정보 저장
total : 이제까지 점검에 참여한 친구들이 점검한 취약지점 범위(합집합)
cnt : 이제까지 점검에 참여한 친구들 수
end : 점검에 참여할 친구들 수
*/
public boolean permu(int flag, int total, int cnt, int end){
if(cnt == end){//end명 모두 start_point(취약지점) 고름
//모든 취약지점이 전부 점검완료했는지 확인
if(total < (Math.pow(2,weak_cnt) - 1)) return false;
return true;
}
for(int i = 0; i < weak_cnt; i++){
if((flag & (1 << i)) > 0) continue;//i번째 취약지점 위치 선택함
if(permu(flag | (1 << i), total | fr[cnt][i], cnt+1, end)) return true;
}
return false;
}
}
리뷰
- 처음에 시계방향과 반시계방향으로 모두 이동 가능하다고 해서 취약지점마다 양 방향에 따른 점검범위를 각각 저장하고, dfs(permutation)시에도 시계방향으로 도는 경우와 반시계방향으로 도는 경우를 각각 체크해야한다고 생각함
- 이럴경우 당연하게도 시간초과가 남..
- 어차피 permutation을 구하면서 위치를 고려하여 모든 경우의 수를 따지기 때문에 도는 방향은 중요하지 X, 범위가 중요!
- 처음에 비트마스크를 활용할 생각을 못하고, 그냥 permutation을 구할 때마다 매번 점검범위를 확인해주었음
- 시간초과! => 뒤늦게 비트마스크로 바꾸어 풀어서 시간이 너무 오래 걸림..!
- 비트마스크를 활용하게 되면 or, and 연산과 크기비교로 모든 취약지점이 점검되었는지를 반복문 없이 코드 한 줄로 확인이 가능함..
- 문제를 읽고 무시해도 되는 조건과 챙겨가야 할 조건을 잘 구분할 줄 알아야 함!