반응형
비트마스킹을 이용해 m개 이하의 치킨집을 연 후 치킨거리를 게산하여 최솟값을 출력하는 문제였습니다.
풀이방법
시간복잡도 : (살릴 치킨집을 고르는 시간) * (다 고른 후 도시의 치킨 거리를 구하는 시간) = (2^m) * n^2
1. n^n의 격자에서 입력 받을 때 집의 좌표와 치킨집의 좌표를 각자 저장합니다.
2. 비트마스킹을 이용해 치킨집이 열려있는 상태를 표시할 수 있습니다.
2-1. i개의 치킨집들 중 최대 m개를 선택하여 나올 수 있는 최소 도시치킨 거리를 찾습니다. 비트마스킹으로 모든 상태를 표시하므로 연 치킨집의 수가 m개를 초과하면 치킨거리를 구하지 않습니다.
2-2. 각자 집의 좌표에 대해 치킨집의 좌표들 까지의 맨해튼 거리를 구해 최소를 구하고 도시치킨 거리의 좌표에 더해줍니다. 이렇게 모든 집의 좌표에 대해 도시치킨 거리의 좌표를 구하면 거리를 반환해줍니다.
3. 이들 치킨 거리들 중 최소를 출력합니다.
Code
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int n,m;
int city[51][51];
int ans = 0x3f3f3f3f;
struct home { int x,y; };
struct chicken { int x,y,opened; };
vector <home> homes;
vector <chicken> chickens;
int getDistance(int x1, int y1, int x2, int y2){
return abs(x1-x2) + abs(y1-y2);
}
int getChickDist(){
int dist = 0;
for(int i = 0; i < homes.size(); i++){
int tmp = 101;
for(int j = 0; j < chickens.size(); j++){
if(chickens[j].opened){
int x1 = homes[i].x;
int y1 = homes[i].y;
int x2 = chickens[j].x;
int y2 = chickens[j].y;
tmp = min(tmp, getDistance(x1,y1,x2,y2));
}
}
dist += tmp;
}
return dist;
}
int main(){
cin >> n >> m;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> city[i][j];
if(city[i][j] == 1) homes.push_back({i,j});
else if(city[i][j] == 2) chickens.push_back({i,j,0});
}
}
for(int i = 0; i < (1 << chickens.size()); i++){
int chickenStat = 0;
int tmp = i;
while(tmp){
chickenStat += tmp % 2;
tmp/= 2;
}
if(chickenStat > m) continue;
for(int j = 0; j < chickens.size(); j++){
chickens[j].opened = i & (1<<j);
}
ans = min(ans,getChickDist());
}
cout << ans;
}
'Algorithm > Implementation' 카테고리의 다른 글
(C++) - 프로그래머스(월간코드챌린지) : 쿼드압축 후 개수 세기 (0) | 2020.12.28 |
---|---|
(Javascript) - 프로그래머스(2019 카카오 겨울 인턴) : 징검다리 답 (0) | 2020.12.27 |
(C++) - 백준(BOJ) 17219번 : 비밀번호 찾기 답 (0) | 2020.10.07 |
(Javascript) - 백준(BOJ) 11005번 : 진법 변환 2 (0) | 2020.10.03 |
(C++) - 백준(BOJ) 11286번 : 절댓값 힙 답 (0) | 2020.10.03 |