BOJ : 17142 연구소 3

---

[BOJ 17142(G4) 리뷰]

지난 연구소, 연구소 2 문제에 이어 다른버전의 문제이다.

근데 연구소 2 문제와 코드 한줄차이라 올릴까 말까 고민했다.

문제 설명을 잘 보면 지난 연구소 2와 동일한 조건인데, 기존에 바이러스였던 위치는 새로 바이러스가 퍼지는것이 아니므로 퍼지는 시간을 계산할때 포함시키지 않는다는 소리다.

그렇기에 아래처럼 방문한 곳이 기존의 바이러스 위치라면 거리값을 return 할때 포함하지 않도록 했다.

너무 간단해서 뭔가 놓친게 있나 싶어 문제를 다시 읽어봤는데 별 다른 문제점을 못찾길래 제출했더니 정답이 나왔다.

(솔직히 정답나올지 몰랐음 이왜맞??..)

---

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <string>
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();
		if (map[cur.X][cur.Y]!=2)
			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;
	
	
}