백준 Gold 3 연구소 3

연구소 3 (백준 Gold 3)

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

N x N 개의 맵 정보가 주어진다

• 2는 비활성화된 바이러스
  (활성화 되면 상하좌우로 시간마다 퍼진다)
  (비활성화된 바이러스는 활성화된 바이러스가 들어오면 활성화 됨)
  

• 1은 벽
  

• 0은 빈 공간(이를 통해 바이러스가 퍼질 수 있다)
  

주어진 비활성화된 바이러스 들 중 M개를 활성화한다고 가정하였을 때
모든 칸에 바이러스를 퍼뜨릴 수 있는 최소 시간을 구하는 문제

• 바이러스를 전부 퍼뜨릴 수 없는 구조라면 -1을 출력
  

풀이 방법

단순한 BFS 문제라 생각하였으나
맵의 바이러스 개수가 M의 개수가 아니기에
그 중 ‘선택’한 녀석들만 활성화 시키는 문제이다

백트래킹!

임의의 M개를 선택하고 그 M개를 BFS를 태워 구하는 문제

• 다만 ‘비활성 바이러스’에서 ‘바이러스’가
  활성화 되는 것은 별도의 시간 계산을 할 필요가 없기에
  이 부분에서 꽤 난항을 먹었다
  

• 그렇기에 각각의 방문 시간을 기록하고(visit)
  map에서 원래 0인 (빈공간)
  칸들의 값만 세어주는 쪽으로 로직을 수정하여 풀 수 있었다
  

제출 코드

#include<iostream>
#include<vector>
#include<queue>
#include<limits.h>

using namespace std;

const int dirY[4] = { 0,-1,0,1 };
const int dirX[4] = { -1,0,1,0 };

int n, m;

struct infos
{
	int y, x;
	int time;
};

struct Compare
{
	bool operator()(infos& a, infos& b)
	{
		return a.time > b.time;
	}
};

int mapCount(const vector<vector<int>>& maps, const vector<vector<int>>& visit)
{
	int ret = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (maps[i][j] == 0)
			{
				if(visit[i][j] == -1)
					return -1;

				if (ret < visit[i][j])
					ret = visit[i][j];
			}
		}
	}

	return ret;
}

int bfs(const vector<vector<int>>& maps, const vector<pair<int, int>>& vPoss, vector<pair<int, int>>& startP)
{
	vector<vector<int>> visit(n, vector<int>(n, -1));

	priority_queue<infos, vector<infos>, Compare> pq;

	for (auto& p : startP)
	{
		visit[p.first][p.second] = 0;
		pq.push({ p.first,p.second,0 });
	}

	int ans = 0;

	while (pq.empty() == false)
	{
		int nowY = pq.top().y;
		int nowX = pq.top().x;
		int nowTime = pq.top().time;
		pq.pop();

		for (int i = 0; i < 4; i++)
		{
			int ny = nowY + dirY[i];
			int nx = nowX + dirX[i];
			int nCost = nowTime + 1;

			if (ny < 0 || ny >= n ||
				nx < 0 || nx >= n)
				continue;

			// 벽
			if (maps[ny][nx] == 1)
				continue;

			if (visit[ny][nx] > 0)
				continue;

			visit[ny][nx] = nCost;

			pq.push({ ny,nx,nCost });
		}
	}

	return mapCount(maps, visit);
}

int recur(vector<vector<int>>& maps, vector<pair<int, int>>& vPoss, int now, vector<pair<int, int>>& poss)
{
	if (poss.size() == m)
	{
		return bfs(maps, vPoss, poss);
	}

	int vSize = vPoss.size();

	if (now == vSize)
		return -1;

	int ret = INT_MAX;
	bool bAllFail = true;


	for (int i = now; i < vSize; i++)
	{
		poss.push_back(vPoss[i]);

		int r = recur(maps, vPoss, i + 1, poss);
		if (r != -1)
		{
			bAllFail = false;
			if (r < ret)
				ret = r;
		}

		poss.pop_back();
	}

	if (bAllFail)
		return -1;

	return ret;
}

int main()
{
	cin >> n >> m;
	vector<vector<int>> maps(n, vector<int>(n, 0));
	vector<pair<int, int>> vPoss;
	vPoss.reserve(m);

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> maps[i][j];
			if (maps[i][j] == 2)
				vPoss.push_back({ i,j });

		}
	}

	vector<pair<int, int>> temp;

	cout << recur(maps, vPoss, 0, temp);

	return 0;
}

결과

생각보다 구현에 시간을 많이 사용한 문제

문제를 잘 읽어야 하며
동시에 가벼운 발상의 전환 역시 중요하다는 것을
리마인드 한 문제이다