[백준 28283번] 해킹 C++ 풀이

1. 문제 

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

28283번: 해킹

$ N $개의 컴퓨터가 주어지고 $ M$개의 통신망의 정보가 주어진다. 두개의 컴퓨터를 연결하는 통신망은 1개 이하이다.

%$X$ 개의 컴퓨터를 동시에 해킹하는데 1분마다 해당 컴퓨터의 가중치값인 돈을 얻을수있다. 또한 해킹한 이후 $0.5$ 분정부에서 $Y$개의 컴퓨터에 보안 시스템을 설치한다. 이때 1분 마다 컴퓨터에서 돈을 얻을때 컴퓨터에 보안 시스템이 설치되었다면 해당 컴퓨터에서는 더 이상 돈을 얻을 수 없다. 보안 시스템은 한번 설치하면 계속 유지되고 1분마다 보안 시스템이 설치된 컴퓨터와 연결된 컴퓨터에 보안 시스템이 설치될때 얻을 수 있는 돈의 최대값을 구해야한다.( 답이 무한대이면 -1)

 

2. 접근

먼제 보안시스템이 주위에 연결된 컴퓨터로 퍼저 나간다는 점에서 BFS을 생각해볼수있다. 

BFS를 통해 탐색을 하면서 방문한 컴퓨터에 대해 컴퓨터에서 얻을 수 있는 돈 $ A_i$ 와 이때의 시간 정보를 곱하여 컴퓨터 마다 얻을 수 있는 돈의 최대값을 구한뒤, 최댓값이 높은 기준으로 선택하여 더하면 답을 구할 수 있다.

무한대인 답을 처리할때, 탐색을 하지 못한 컴퓨터가 존재해도 이때의 $ A_i$가 0이라면 무한대가 아님을 주의해야한다.

 

3. 구현

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

using namespace std;
vector<int> vec[500001];
int visited[500001] = { 0 };

long long result1[500001] = { 0 };
long long result2[500001] = { 0 };
queue <int>que1;//간선 정보
queue <int>que2;//
int N, M, X, Y;
bool compare(int a, int b) {
	return a > b;
}
void bfs() {
	int node;
	int day = 0;
	while (!que1.empty()) {
		node = que1.front();
		day = que2.front();
		que1.pop();
		que2.pop();
		if (visited[node] != 0)
			continue;
		visited[node] = 1;
		result2[node] = result1[node] * day;
		for (int i = 0; i < vec[node].size(); i++) {
			que1.push(vec[node][i]);
			que2.push(day + 1);
		}
	}



	return;
}
int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> M >> X >> Y;
	for (int i = 1; i <= N; i++) {
		cin >> result1[i];
	}
	int temp1, temp2;
	for (int i = 1; i <= M; i++) {
		cin >> temp1 >> temp2;
		vec[temp1].push_back(temp2);
		vec[temp2].push_back(temp1);
	}
	for (int i = 1; i <= Y; i++) {
		cin >> temp1;
		que1.push(temp1);
		que2.push(0);
	}
	bfs();
	sort(result2 + 1, result2 + 1 + N,compare);
	long long sum = 0;
	for (int i = 1; i <= N; i++) {
		if (visited[i] == 0 && result1[i] > 0) {
			cout << -1;
			return 0;
		}
	}
	for (int i = 1; i <= X; i++) {
		
		sum = sum + result2[i];
	}
	cout << sum;
	return 0;
}