골드4 - 백준 17142 연구소 3

백준 17142 연구소 3

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

접근방법

바이러스를 선택하는 모든 조합을 구했고, 선택된 조합으로 BFS를 진행하여 가장 오래 걸리는 시간을 찾아주었다. Min값을 갱신해가며 그 중에서 가장 작은 값을 선택하였고, 출력해주었다.

풀이

DFS를 이용하여 모든 조합을 구했다. M개만큼 바이러스가 선택되면 BFS를 진행시켰다. BFS는 선택된 바이러스를 queue에 넣었고 벽, 이미 방문한 지점들은 제외하고 모든 지점까지의 최단 거리를 구하였다. 그리고 전체 방문 거리들을 탐색하며 지점들 중 가장 먼 지점의 시간값을 저장해주었고 반환하였다. BFS함수에서 반환한 값으로 기존에 저장된 Min과 비교하며 가장 최소값을 찾아주어 출력해주었다.

코드

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

using namespace std;
int lab[50][50];
int visited[50][50];
vector<pair<int, int>> virus;
vector<int> sel;
int Min = 100000;
int N, M;
vector<vector<int>> dir = { {0,1}, {0,-1}, {1,0}, {-1,0} };

int BFS()
{
	memset(visited, -1, sizeof(visited));
	queue<pair<int, pair<int, int>>> q;
	for (int i = 0; i < sel.size(); i++)
	{
		visited[virus[sel[i]].first][virus[sel[i]].second] = 0;
		q.push({ 0, {virus[sel[i]].first, virus[sel[i]].second} });
	}

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

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

			if (nx < 0 || nx >= N || ny < 0 || ny >= N)
				continue;
			if (lab[nx][ny] == 1)
				continue;
			if (visited[nx][ny] != -1 && visited[nx][ny] <= dis + 1)
				continue;

			visited[nx][ny] = dis + 1;
			q.push({ dis + 1, {nx, ny} });
		}
	}

	int Max = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (lab[i][j] == 1)
				continue;
			if (lab[i][j] == 2)
				continue;
			if (visited[i][j] == -1)
				return 100000;
			Max = max(visited[i][j], Max);
		}
	}

	return Max;
}

void DFS(int start, int depth)
{
	if (depth == M)
	{
		int result = BFS();
		Min = min(result, Min);
		return;
	}

	for (int i = start; i < virus.size(); i++)
	{
		sel.push_back(i);
		DFS(i + 1, depth + 1);
		sel.pop_back();
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> lab[i][j];

			if (lab[i][j] == 2)
				virus.push_back({ i,j });
		}
	}

	DFS(0, 0);

	if (Min == 100000)
		cout << -1 << endl;
	else
		cout << Min << endl;
	return 0;
}