[BOJ-10282] 해킹

백준 10282 해킹

 

10282번: 해킹

 

문제 설명

 

 - 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다.

 

 - 서로 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다.

 

 - 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다.

  

 - 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며,

   그에 걸리는 시간이 얼마인지 구하라.

 

 - 각 테스트 케이스마다 한 줄에 걸쳐 총 감염되는 컴퓨터 수, 마지막 컴퓨터가 감염되기까지 걸리는 시간을 공백으로 구분지어 출력하라.

---

 

입력 값

 

 - 첫째 줄에 테스트 케이스의 개수가 주어진다.

   테스트 케이스는 최대 100개이다. 

 

 - 각 테스트 케이스는 첫째 줄에 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터의 번호 c가 주어진다.

   ( 1 <= n <= 10,000, 1 <= d <= 100,000, 1 <= c <= n )

 

 - 이어서 d개의 줄에 각 의존성을 나타내는 정수 a, b, s가 주어진다.

   ( 1 <= a, b <= n, a != b, 0 <= s <= 1,000 )

   컴퓨터 a가 컴퓨터 b를 의존하며, 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염된다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 해킹 당한 컴퓨터를 시작으로 의존성을 검사하여, 총 몇 대의 컴퓨터가 감염되고, 그에 걸리는 시간을 구하는 문제이다.

 

 - 해당 컴퓨터가 감염되는 시간은 가장 먼저 해당 컴퓨터에 도달했을 때 이다.

 

 - 즉, 3번 컴퓨터가 5라는 시간에 감염이 되었다면, 다른 의존성에 의해 6, 7, 8.. 등의 시간에 감염이 이루어지더라도

   결국은 5라는 시간에 감염이 되었다는 것이다.

 

 - 결론적으로 이 문제는 시작 컴퓨터를 기준으로 다른 컴퓨터까지 걸리는 최단 시간을 구하는 문제이다.

 

 - 컴퓨터 사이에 감염되는 시간 s는 모두 양수이기 때문에 다익스트라를 이용하면 간단하게 해결할 수 있다.

최단 경로 탐색 알고리즘 - 다익스트라(Dijkstra)

 

---

 

 

소스 코드

 

#include <bits/stdc++.h>
#include<unordered_map>
using namespace std;

int n, d, c;
int a, b, s;

int visited[10001];

pair<int, int> Dijkstra(int start, vector<vector<pair<int, int>>> &v) {

	priority_queue<pair<int, int>> pq;


	fill_n(visited, 10001, INT_MAX);

	visited[start] = 0;

	pq.push({ 0,start });

	while (!pq.empty()) {
		int startNode = pq.top().second;
		int startCost = -pq.top().first;
		pq.pop();

		if (visited[startNode] > startCost) {
			continue;
		}

		for (auto next : v[startNode]) {
			int nextNode = next.first;
			int nextCost = next.second;


			if (visited[nextNode] <= startCost + nextCost) {
				continue;
			}
			visited[nextNode] = startCost + nextCost;

			pq.push({ -visited[nextNode],nextNode });


		}

	}

	int maxLength = 0;
	int cnt=0;

	for (int i = 1; i <= n; i++) {
		if (visited[i] == INT_MAX) {
			continue;
		}
		maxLength = max(maxLength, visited[i]);
		cnt++;
	}

	return{ cnt,maxLength };
}

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

	int t;
	cin >> t;

	
	while (t--) {
		cin >> n >> d >> c;
		vector<vector<pair<int, int>>> v(n+1);

		for (int i = 0; i < d; i++) {
			cin >> a >> b >> s;
			v[b].push_back({ a,s });
		}

		pair<int, int> result = Dijkstra(c, v);

		cout << result.first << " " << result.second << "\n";


	}


	return 0;
}