이문제는 처음에 bfs로 접근 했다 bfs로 풀었을 때는 각 지점에서 bfs로 확장해나가다가 치킨집이 모든 집을 방문했을 때의 각치킨집의 거리합을 이용해서 최솟값을 도출했으나 시간초과가 발생하였다. 의외로 이 문제는 간단하게 풀리는 문제 였다 그냥 치킨집에서 N개를 뽑아서 얘네들을 집과의 거리를 구해서 집과 치킨의 최소 거리를 저장해준 후 이를 계속 비교해가며 최솟값을 찾는 문제였다. 백트랙킹을 이용한 조합을 사용하여 풀었다.
#include <iostream>
#include <vector>
#include <utility>
#define MAX_INT 2147483647
using namespace std;
int N, M;
vector<pair<int, int>> chickenPos;
bool isVisited[50] = { 0, };
vector<pair<int, int>> housePos;
vector<pair<int, int>> selectedChicken;
int minCityDistance=MAX_INT;
void calculateDistance() {
int distanceOfCity = 0;
for (int i = 0; i < housePos.size(); i++) {
int minDistance = MAX_INT;
for (int j = 0; j < selectedChicken.size(); j++) {
int distance = abs(housePos[i].first - selectedChicken[j].first) + abs(housePos[i].second - selectedChicken[j].second);
if (distance < minDistance) {
minDistance = distance;
}
}
distanceOfCity += minDistance;
}
if (distanceOfCity < minCityDistance) {
minCityDistance = distanceOfCity;
}
}
void selectChicken(int idx, int level) {
if (level == M) {
calculateDistance();
return;
}
for (int i = idx; i < chickenPos.size(); i++) {
if (!isVisited[i]) {
isVisited[i] = true;
selectedChicken.push_back(chickenPos[i]);
selectChicken(i , level + 1);
isVisited[i] = false;
selectedChicken.pop_back();
}
}
}
int main() {
ios::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M;
int tmp;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> tmp;
if (tmp == 2) {
chickenPos.push_back(make_pair(i, j));
}
else if (tmp == 1) {
housePos.push_back(make_pair(i, j));
}
}
}
selectChicken(0,0);
cout << minCityDistance;
}
일단 이 코드의 이 부분 부터 보자
void selectChicken(int idx, int level) {
if (level == M) {
calculateDistance();
return;
}
for (int i = idx; i < chickenPos.size(); i++) {
if (!isVisited[i]) {
isVisited[i] = true;
selectedChicken.push_back(chickenPos[i]);
selectChicken(i , level + 1);
isVisited[i] = false;
selectedChicken.pop_back();
}
}
}
이 부분은 일단 치킨집의 좌표들이 저장되어있는 chickenPos vectory 에서 치킨을 선택한 후 에 selectedChicken 에 넣어준다 그후 isVisited를 true로 설정해 주어 방문했다고 한 뒤 다쓰고 나면 false로 바꿔주고 selectedchicken 벡터에서 제거해 준다. 그후 level이 M 즉 M개의 치킨집을 뽑았으면 calculate distance 함수를 실행한다.
void calculateDistance() {
int distanceOfCity = 0;
for (int i = 0; i < housePos.size(); i++) {
int minDistance = MAX_INT;
for (int j = 0; j < selectedChicken.size(); j++) {
int distance = abs(housePos[i].first - selectedChicken[j].first) + abs(housePos[i].second - selectedChicken[j].second);
if (distance < minDistance) {
minDistance = distance;
}
}
distanceOfCity += minDistance;
}
if (distanceOfCity < minCityDistance) {
minCityDistance = distanceOfCity;
}
}
이 함수의 로직도 매우 간단하다 아까 이전 함수에서 뽑은 치킨집들이랑 각 집과 의 거리를 구하고 각집마다 치킨집에서 가장 가까운 거리를 minDistance에 저장한다 그후 각집의 치킨집까지의 최솟값을 더한후 이전에 뽑았던 최솟값과 비교를 해서 작은애를 다시 넣어준다.