BOJ : 17141 연구소 2

 

 

---

[BOJ 17141(G5) 리뷰]

지난번 풀었던 연구소 문제의 다른 버전이다.

저번엔 백트래킹으로 풀었지만 이번엔 next_permutation 함수를 이용했다.

지난번에는 벽을 세워 바이러스를 막아야했다면 이번엔 바이러스를 퍼지게할 위치를 고른다음 가장 빨리 바이러스가 퍼지는 위치에서 바이러스가 퍼지는 시간의 최소값을 출력해야한다.

그냥 주어진 시뮬레이션대로 구현하면 되는거라 별도의 디버깅없이 한번에 구현하고 바로 정답처리가 되었다.

 

1.먼저 next_permutation함수를 이용해서 총 K개의 바이러스 중 M개의 바이러스를 선택하여 벡터에 담는다.

2.선택된 바이러스의 좌표값을 기준으로 BFS를 수행하여 최대 DIST배열을 통해 최대 거리를 측정한다.

3.바이러스가 끝까지 퍼지지 않았다면 그 값은 무효하므로 check함수를 통해 바이러스가 끝까지 퍼졌는지 확인하고 끝까지 퍼졌을 경우에만 올바른 값을 return한다.

4.return된 값 중 최소값을 출력하면 된다. 최소값이 INF라면 모든 경우에서 바이러스가 끝까지 퍼지지 못했으므로 -1을 출력하면 된다.

 

위 로직으로 바이러스 위치를 선택할 수 있는 모든경우에 대해 수행하면 된다.

깔끔하게 코드가 써지고 딱 정답처리되어 기분이 좋았다.

 

 

---

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;
#define X first
#define Y second
#define INF 987654321

int map[51][51];
int dist[51][51];
vector <pair<int, int>> virus;
queue <pair<int, int>> start;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int N, M;
int ans = INF;


int check() //끝까지 바이러스가 퍼졌는지 확인
{
	int ret = true;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (dist[i][j] == -1 && map[i][j] != 1)
			{
				ret = false;
				break;
			}
		}
	}
	return ret;
}

int BFS() //최대 거리 반환
{
	int maxret = 0;
	queue <pair<int, int>> Q;
	while (!start.empty())
	{
		auto cur = start.front(); start.pop();
		Q.push({ cur.X,cur.Y });
		dist[cur.X][cur.Y] = 0;
	}

	while (!Q.empty())
	{
		auto cur = Q.front(); Q.pop();
		maxret = max(maxret, dist[cur.X][cur.Y]);
		for (int dir = 0; dir < 4; dir++)
		{
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
			if (dist[nx][ny]!=-1 || map[nx][ny] == 1) continue;
			Q.push({ nx,ny });
			dist[nx][ny] = dist[cur.X][cur.Y] + 1;
		}
	}
	if (check())
		return maxret;
	else
		return INF;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 2)
				virus.push_back({ i,j });
		}
	}
	int size = virus.size();
	vector <int> brute(size, 1);
	fill(brute.begin(), brute.end() - M, 0);

	do
	{
		for (int i = 0; i < N; i++)
			fill(dist[i], dist[i] + N, -1);

		for (int i = 0; i < size; i++)
		{
			if (brute[i] == 0) continue;
			start.push(virus[i]);
		}
		//BFS수행
		int ret = BFS();
		ans = min(ans, ret);
	} while (next_permutation(brute.begin(), brute.end()));

	if (ans == INF) cout << -1;
	else
		cout << ans;
	
	
}