[백준][C++] 10282. 해킹

컴퓨터들의 의존성을 보고 해킹된 컴퓨터 수와 걸리는 시간을 출력하는 문제이다.

 

보자마자 그래프 문제여서 다익스트라를 쓰려고 했는데

너무 오랜만에 다익스트라를 써서 기억이 안났다..

그래서 다익스트라 코드는 아래 블로그를 참조했다. (alswnsdl.tistory.com/13)

다익스트라 알고리즘(Dijkstra's algorithm) C++ 코드

이 문제에서 주의할 점은, 의존성이 a, b, s 순서대로 주어지므로 그래프 방향은 a -> b가 아닌 b -> a 형태로 저장해야 한다는 점이다. (컴퓨터 b가 감염되면 s초 후에 a가 감염되기 때문)

 

입력받은 그래프에 다익스트라 알고리즘을 적용하여 c에 대한 dist 배열을 완성한다.

그리고 dist 배열을 한 바퀴 돌면서,

만약 INF가 아닌 정수가 나오면 해당 컴퓨터가 감염이 되었다는 뜻이므로 감염 컴퓨터 수에 +1을 해준다.

또한 마지막 컴퓨터가 감염되기까지 걸리는 시간은 dist 배열에서 INF가 아닌 정수 중 최대값이다.

 

다익스트라만 할 줄 알면 되는 문제라 바로 맞을 줄 알았는데

자꾸 답이 이상하게 나와서 삽질을 좀 했다...

 

처음에 내가 그래프 벡터를 습관처럼 전역 변수로 설정해줬는데, 각 테스트케이스마다 이를 초기화해주지 않아 계산이 제대로 안된 거였다. 그래서 그냥 지역변수로 설정해주고 함수 인자를 변경해주니까 잘 풀렸다.

 

 

// 10282_해킹.cpp
using namespace std;
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <cstring>
#define INF 987654321
#define MAX 10001

int infect; // 감염 컴퓨터 수
int infect_sec; // 마지막 컴퓨터가 감염되기까지 걸린 시간

void dijkstra(vector<vector<pair<int, int>>> graph, int start, int n) {
	priority_queue<pair<int, int>> pq;
	vector<int> dist(n + 1, INF);

	pq.emplace(0, start); // 시작점 push
	dist[start] = 0;

	while (!pq.empty()) {
		int cur_dist = -pq.top().first; // 방문할 점의 dist (감염시간) (오름차순)
		int cur = pq.top().second; // 방문할 정점

		pq.pop();

		for (auto &p : graph[cur]) {
			int next = p.first; // 다음 정점
			int next_dist = p.second + cur_dist; // 다음 정점의 감염시간

			if (dist[next] > next_dist) {
				dist[next] = next_dist;
				pq.emplace(-dist[next], next);
			}
		}
	}

	// 감염된 컴퓨터 수 & 감염 시간 계산
	for (int i = 1; i <= n; i++) {
		if (dist[i] != INF) { // dist가 INF가 아니면 방문한 것이므로 감염된 것
			infect += 1;
			if (dist[i] > infect_sec) infect_sec = dist[i];
		}
	}
}

int main() {
	int T;
	scanf("%d", &T);

	for (int tc = 0; tc < T; tc++) {
		int n, d, c;
		scanf("%d %d %d", &n, &d, &c);

		vector<vector<pair<int, int>>> hack(n + 1);
		for (int i = 0; i < d; i++) {
			int a, b, s;
			scanf("%d %d %d", &a, &b, &s);
			hack[b].emplace_back(a, s);
		}

		infect = 0;
		infect_sec = 0;
		dijkstra(hack, c, n);

		printf("%d %d\n", infect, infect_sec);
	}

	return 0;
}