[BOJ 10282 // C++] 해킹

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 10282번 문제인 해킹이다.
문제는 아래 링크를 확인하자.

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

10282번: 해킹

각 컴퓨터를 노드로, 컴퓨터 사이 의존관계를 가중치를 가진 에지로 생각하자.

 

x가 y를 의존하면 y가 감염되었을 시 일정 시간 후 x를 감염시킨다는 의미이므로, y에서 x방향으로 가는 가중치 s의 에지를 생각할 수 있다.

 

감염된 컴퓨터의 개수는 dijkstra 알고리즘을 돌리는 과정에서 새로운 노드의 거리를 확정지을 때마다 계수하는 것으로 구할 수 있다.

 

가장 마지막에 감염된 컴퓨터는 dijkstra 알고리즘의 특징상 방문 가능한 가장 먼 노드를 마지막에 방문하게 된다는 특징을 이용하여 dijkstra 알고리즘을 돌리면서 등장하는 그때그때의 최단거리를 계속 갱신하는 것으로 구할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

priority_queue<pair<int, int>> pq;
vector<pair<int, int>> G[10001];
int dist[10001];
int visited[10001];
int cnt;
int ans;
void dijkstra() {
	while (!pq.empty()) {
		int current = pq.top().second, d = -pq.top().first; pq.pop();
		if (visited[current]) continue;
		visited[current] = 1;
		cnt++; ans = d;
		for (auto node : G[current]) {
			if (visited[node.second]) continue;
			pq.push({ -(d + node.first),node.second });
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) {
		cnt = 0;
		int N, D, C; cin >> N >> D >> C;
		for (int i = 1; i <= N; i++) G[i].clear();
		memset(dist, 0, sizeof(dist));
		memset(visited, 0, sizeof(visited));
		while (D--) {
			int x, y, s; cin >> x >> y >> s;
			G[y].push_back({ s,x });
		}

		pq.push({ 0,C });
		dijkstra();

		cout << cnt << ' ' << ans << '\n';
	}
}