[백준OJ] 15686번 치킨 배달

www.acmicpc.net/problem/15686

15686번: 치킨 배달

---

 

-풀이-

1. 입력을 받을때 치킨집의 위치를 모두 vector에 넣어준다.

2. 입력받은 치킨집중 M개를 고른다.

3. 고른 M개의 치킨집을 기준으로, 모든 집까지의 최소거리를 bfs를 통해 구해준다.

4. 모든 집에는 최소 거리가 저장되어있으므로, 집들을 탐색하며 거리를 모두 더해준 뒤, 최솟값을 갱신해준다.

 

-시간복잡도-

먼저 최대 13개중 M개를 고르는 시간은 조합을 이용하여 O(13 C M) 이 걸린다. 하지만 이는 최대 1716이 나오므로, 상수시간이라고 봐도 된다.

고른 각각의 M개의 치킨집에 대하여 BFS를 수행하는데 걸리는 시간은 O(N*N) 이 된다. 또한 BFS탐색 후 집을 탐색하며 거리를 더해주는 로직또한 O(N*N)이 걸리므로 총 O(N*N)이 된다.

 

따라서 이 문제의 시간복잡도는 O(N*N) 이 된다.

 

-코드-

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define INF 987654321
using namespace std;

int n, m;
int maze[51][51];
int mv[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
int result = INF;
vector<pair<pair<int, int>,bool>> chicken;

bool isIn(int x, int y) {
	return x >= 0 && x < n&&y >= 0 && y < n;
}

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> maze[i][j];
			if (maze[i][j] == 2) {
				chicken.push_back({ { i,j } ,false});
			}
		}
	}
}

void bfs() {
	queue<pair<int, int>> q;
	int dist[51][51];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dist[i][j] = INF;
		}
	}
	for (int i = 0; i < chicken.size(); i++) {
		if (chicken[i].second) {
			q.push({ chicken[i].first.first,chicken[i].first.second });
			dist[chicken[i].first.first][chicken[i].first.second] = 0;
		}
	}

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + mv[i][0];
			int ny = y + mv[i][1];

			if (isIn(nx, ny)&&dist[nx][ny]==INF) {
				dist[nx][ny] = dist[x][y] + 1;
				q.push({ nx,ny });
			}
		}
	}
	int s = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (maze[i][j] == 1) {
				s += dist[i][j];
			}
		}
	}
	result = min(result, s);
	return;
}

void dfs(int now, int cnt) {
	if (now == chicken.size()) {
		return;
	}
	if (cnt == m) {
		bfs();
		return;
	}
	for (int i = now + 1; i < chicken.size(); i++) {
		chicken[i].second = true;
		dfs(i, cnt+1);
		chicken[i].second = false;
	}
}

void solve() {
	for (int i = 0; i < chicken.size(); i++) {
		chicken[i].second = true;
		dfs(i, 1);
		chicken[i].second = false;
	}
	cout << result << "\n";
}

int main(){
	input();
	solve();
}