[#15686] 치킨 배달

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;

map<pair<int, int>, int> houseIndex;  //row, col에서 집 index 찾아내려고 쓴 map
vector<vector<int>> board;
vector<pair<int, int>> houseVec;  //집 위치 저장하는 vector
vector<pair<int, int>> chickenVec;  //치킨집 위치 저장하는 vector
vector<vector<int>> dist;  //[치킨집 번호][집 번호] 거리
vector<int> minDist;  //각 집의 최소 치킨거리
int houseNum;  //집 갯수
int chickenNum;  //치킨집 갯수
int n, m;
int ans = 10000000000;

//동서남북
int dRow[4] = { 0,0,1,-1 };
int dCol[4] = { 1,-1,0,0 };

//범위 안에 있는지 검사
bool inRange(int row, int col) {
	if (1 <= row && row < n + 1 && 1 <= col && col < n + 1)
		return true;

	return false;
}

//치킨집 번호, 시작 치킨집 row, 시작 치킨집 col
//치킨집을 시작으로 bfs 돌려서 각 집까지의 거리 구하기
void bfs(int cnt, int row, int col) {
	queue<pair<int, int>> q;
	vector<vector<int>> distance(n + 1, vector<int>(n + 1, -1));

	q.push({ row, col });
	distance[row][col] = 0;

	while (!q.empty()) {
		int hereRow = q.front().first;
		int hereCol = q.front().second;
		int hereDist = distance[hereRow][hereCol];

		//집이라면
		if (board[hereRow][hereCol] == 1) {
			int index = houseIndex[{hereRow, hereCol}];  //row, col에서 집 index 알아내기
			dist[cnt][index] = hereDist;  //dist에 저장
		}

		q.pop();

		for (int i = 0; i < 4; i++) {
			int thereRow = hereRow + dRow[i];
			int thereCol = hereCol + dCol[i];

			if (inRange(thereRow, thereCol) && distance[thereRow][thereCol] == -1) {
				q.push({ thereRow, thereCol });
				distance[thereRow][thereCol] = hereDist + 1;
			}
		}
	}
}

//cnt번재 고를거야
void recursive(int cnt, int index, vector<int>& select) {
	if (cnt == m + 1) {
		//select에 m개

		//모든 집에대해 최소 치킨 거리 구하기
		for (int j = 0; j < houseNum; j++) {
			int tempMin = 1000000;
			for (int k = 0; k < select.size(); k++) {
				int i = select[k];  //select에서 고른 치킨집만
				tempMin = min(dist[i][j], tempMin);
			}
			minDist[j] = tempMin;
		}

		int tempAns = 0;
		for (int i = 0; i < minDist.size(); i++) {
			tempAns += minDist[i];  //각 집의 치킨 거리 더하기
		}
		ans = min(ans, tempAns);

		return;
	}

	for (int i = index; i < chickenNum; i++) {
		select.push_back(i);
		recursive(cnt + 1, i + 1, select);
		select.pop_back();
	}
}

int main() {
	scanf("%d %d", &n, &m);
	board = vector<vector<int>>(n + 1, vector<int>(n + 1));
	
	int houseCnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &board[i][j]);
			if (board[i][j] == 1) {
				houseVec.push_back({ i,j });
				houseIndex[{i, j}] = houseCnt;
				houseCnt++;
			}
			else if (board[i][j] == 2)
				chickenVec.push_back({ i,j });
		}
	}
	houseNum = houseVec.size();
	chickenNum = chickenVec.size();
	dist = vector<vector<int>>(chickenNum, vector<int>(houseNum));
	minDist = vector<int>(houseNum);

	//////////////////////////////////

	//치킨집 기준 bfs
	for (int i = 0; i < chickenNum; i++) {
		bfs(i, chickenVec[i].first, chickenVec[i].second);
	}

	vector<int> select;
	recursive(1,0, select);

	printf("%d", ans);
	
	return 0;
}

앞으로는 푸는데 걸린 시간도 써야지

소요 시간: 50분

 

치킨 집에서 bfs를 시작할지 집에서 bfs를 시작할지 고민하다가 치킨집은 최대 13개뿐이니까 치킨집에서 bfs를 시작하기로 결정

다른 분들 보니까 dfs 쓰신분도 많던데 난 아직 저 문제를 보고 dfs를 써야겠다는 생각이 안들었다.. 아직 부족하다 많이ㅜ

거리라고해서 무조건 bfs를 돌렸는데 생각해보니 각각 가중치가 있는것도 아니고 거리 공식이 있는데 왜 bfs를 돌렸을까

그냥 치킨집 m개 재귀돌리면서 뽑고 각 집에서 뽑아진 치킨집에 대해 거리 구하면 될걸 너무 어렵게 풀었다 (밑에 코드).... bfs 한번 더 연습한셈 치자

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <math.h>
using namespace std;

vector<vector<int>> board;
vector<pair<int, int>> houseVec;  //집 위치 저장하는 vector
vector<pair<int, int>> chickenVec;  //치킨집 위치 저장하는 vector
int houseNum;  //집 갯수
int chickenNum;  //치킨집 갯수
int n, m;
int ans = 10000000000;

//동서남북
int dRow[4] = { 0,0,1,-1 };
int dCol[4] = { 1,-1,0,0 };

//범위 안에 있는지 검사
bool inRange(int row, int col) {
	if (1 <= row && row < n + 1 && 1 <= col && col < n + 1)
		return true;

	return false;
}

//cnt번재 고를거야
void recursive(int cnt, int index, vector<int>& select) {
	if (cnt == m + 1) {
		//select에 m개

		vector<int> minDist(houseNum, 100000000);

		//모든 집에대해 최소 치킨 거리 구하기
		for (int j = 0; j < houseNum; j++) {
			for (int k = 0; k < select.size(); k++) {
				int i = select[k];  //select에서 고른 치킨집만
				minDist[j] = min(minDist[j], abs(houseVec[j].first - chickenVec[i].first) + abs(houseVec[j].second - chickenVec[i].second));
			}
		}

		int tempAns = 0;
		for (int i = 0; i < minDist.size(); i++) {
			tempAns += minDist[i];  //각 집의 치킨 거리 더하기
		}
		ans = min(ans, tempAns);

		return;
	}

	for (int i = index; i < chickenNum; i++) {
		select.push_back(i);
		recursive(cnt + 1, i + 1, select);
		select.pop_back();
	}
}

int main() {
	scanf("%d %d", &n, &m);
	board = vector<vector<int>>(n + 1, vector<int>(n + 1));
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &board[i][j]);
			if (board[i][j] == 1) 
				houseVec.push_back({ i,j });
			else if (board[i][j] == 2)
				chickenVec.push_back({ i,j });
		}
	}
	houseNum = houseVec.size();
	chickenNum = chickenVec.size();
	
	//////////////////////////////////

	vector<int> select;
	recursive(1, 0, select);

	printf("%d", ans);
	
	return 0;
}

 

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달