백준 15686

이문제는 처음에 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에 저장한다 그후 각집의 치킨집까지의 최솟값을 더한후 이전에 뽑았던 최솟값과 비교를 해서 작은애를 다시 넣어준다.