[BOJ] 백준 17141 연구소2, 17142 연구소 3

문제 링크

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

17141번: 연구소 2

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

17142번: 연구소 3

 

 

바이러스를 놓을 수 있는 자리가 정해져 있고, 그중 M개의 자리를 골라 최대한 빠르게 바이러스를 퍼뜨릴 수 있는 시간을 구해야 합니다.

연구소 2와 연구소 3은 시간제한을 빼면 사실상 같은 문제이므로 함께 포스팅합니다.

 

이걸 어떻게 푸나 싶지만 입력에서 2(바이러스를 놓을 수 있는 칸)의 개수가 10 이하입니다. 따라서 바이러스를 놓을 자리를 완전 탐색으로 구할 수 있습니다.

 

풀이

1) 바이러스를 놓을 수 있는 모든 칸에서 각각 bfs를 돌려 연구소의 각 칸에 바이러스가 퍼지는 시간을 저장해둡니다.

2-1) 완전 탐색으로 바이러스 M개를 배치할 칸들을 결정합니다.

2-2) 바이러스를 배치할 칸이 결정되면 연구소의 모든 칸에 대해, 각 칸마다 바이러스가 퍼지는 최소의 시간을 구하고, 각 칸에서 구한 최소 시간 중 최댓값을 구합니다. 이는 1)에서 저장한 시간으로 쉽게 구할 수 있습니다.

3) 바이러스를 배치하는 모든 경우의 수에 대해, 2-2)에서 구한 최댓값 중 최솟값이 정답이 됩니다.

 

최솟값 최댓값이 반복해서 나와 말장난 같지만 잘 생각해보면 간단한 풀이입니다. 구현 실력이 받쳐주지 않으면 코딩이 어려우실 수도 있습니다. 제 코드상으로 시간 복잡도는 $O(_{10}C_{M} * N^2M)$쯤 되겠네요.

 

예외처리로는 바이러스가 퍼질 수 없는 칸이 있을 경우를 생각해주셔야 합니다. 이때는 -1을 출력합니다.

또 연구소 2는 하던대로 짜시면 되는데, 연구소 3에서는 연구소에 빈칸(0)이 없는 경우 0을 출력해야 합니다.

 

 

정답 코드

연구소 2

	#include <bits/stdc++.h>
	using namespace std;
	using pii = pair<int, int>;
	#define all(x) x.begin(), x.end()
	#define ft first
	#define sd second
	#define INF 0x3f3f3f3f
	int n, m;
	int p[100][100];
	int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
	int dst[10][51][51];
	vector<pii> starts;
	void bfs(int num){
	queue<pii> q;
	pii now = starts[num];
	q.push(now);
	dst[num][now.ft][now.sd] = 0;
	while(!q.empty()){
	int x = q.front().ft;
	int y = q.front().sd;
	q.pop();
	for(int k=0; k<4; k++){
	int nx = x+dx[k], ny = y+dy[k];
	if(0 <= nx && nx < n && 0 <= ny && ny < n){
	if(dst[num][nx][ny] == -1 && p[nx][ny] != 1){
	dst[num][nx][ny] = dst[num][x][y] + 1;
	q.push({nx, ny});
	}
	}
	}
	}
	}
	vector<int> ch;
	int go(int idx){
	if(ch.size() == m){
	int ret = -1;
	for(int i=0; i<n ;i++){
	for(int j=0; j<n ;j++){
	if(p[i][j] == 1) continue;
	int val = INF;
	for(int k: ch){
	if(dst[k][i][j] == -1) dst[k][i][j] = INF;
	val = min(val, dst[k][i][j]);
	}
	ret = max(ret, val);
	}
	}
	return ret;
	}
	if(idx == starts.size()) return INF;
	int ret = INF;
	for(int i=idx; i<starts.size(); i++){
	ch.push_back(i);
	ret = min(ret, go(i+1));
	ch.pop_back();
	}
	return ret;
	}
	int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	memset(dst, -1, sizeof(dst));
	cin>>n>>m;
	int cnt = 0;
	for(int i=0; i<n; i++){
	for(int j=0; j<n; j++){
	cin>>p[i][j];
	if(p[i][j] == 2) starts.emplace_back(i, j);
	}
	}
	for(int i=0; i<starts.size(); i++){
	bfs(i);
	}
	int ans = go(0);
	if(ans == INF) ans = -1;
	cout<<ans;
	}

view raw .cpp hosted with ❤ by GitHub

 

 

연구소 3

	#include <bits/stdc++.h>
	using namespace std;
	using pii = pair<int, int>;
	#define all(x) x.begin(), x.end()
	#define ft first
	#define sd second
	#define INF 0x3f3f3f3f
	int n, m;
	int p[100][100];
	int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
	int dst[10][51][51];
	vector<pii> starts;
	void bfs(int num){
	queue<pii> q;
	pii now = starts[num];
	q.push(now);
	dst[num][now.ft][now.sd] = 0;
	while(!q.empty()){
	int x = q.front().ft;
	int y = q.front().sd;
	q.pop();
	for(int k=0; k<4; k++){
	int nx = x+dx[k], ny = y+dy[k];
	if(0 <= nx && nx < n && 0 <= ny && ny < n){
	if(dst[num][nx][ny] == -1 && p[nx][ny] != 1){
	dst[num][nx][ny] = dst[num][x][y] + 1;
	q.push({nx, ny});
	}
	}
	}
	}
	}
	vector<int> ch;
	int go(int idx){
	if(ch.size() == m){
	int ret = -1;
	for(int i=0; i<n ;i++){
	for(int j=0; j<n ;j++){
	if(p[i][j] != 0) continue;
	int val = INF;
	for(int k: ch){
	if(dst[k][i][j] == -1) dst[k][i][j] = INF;
	val = min(val, dst[k][i][j]);
	}
	ret = max(ret, val);
	}
	}
	return ret;
	}
	if(idx == starts.size()) return INF;
	int ret = INF;
	for(int i=idx; i<starts.size(); i++){
	ch.push_back(i);
	ret = min(ret, go(i+1));
	ch.pop_back();
	}
	return ret;
	}
	int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	memset(dst, -1, sizeof(dst));
	cin>>n>>m;
	int cnt = 0;
	for(int i=0; i<n; i++){
	for(int j=0; j<n; j++){
	cin>>p[i][j];
	if(p[i][j] == 2) starts.emplace_back(i, j);
	if(p[i][j] == 0) cnt++;
	}
	}
	if(cnt == 0){
	cout<<0;
	return 0;
	}
	for(int i=0; i<starts.size(); i++){
	bfs(i);
	}
	int ans = go(0);
	if(ans == INF) ans = -1;
	cout<<ans;
	}

view raw .cpp hosted with ❤ by GitHub