백준 Gold 4 해킹

해킹 (백준 Gold 4)

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

테스트 케이스 t개 주어진다
각 테스트 마다

• 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터 c가 주어진다
  
• 이후 d개의 줄에
  
  • a,b,s가 주어진다
    
  • a 컴퓨터는 b 컴퓨터에 의존하기에 b가 감염되면 ‘s’ 초 후에 감염된다
    

c에서 감염이 시작되었을 때
각 테스트마다
총 감염된 컴퓨터 수 + 감염에 걸리는 시간을 구하는 문제

풀이 방법

이 문제의 특징은 ‘단방향’ 그래프라는 점이다

• 단방향으로 주어지는 Edge를 통해
  c에서 다른 컴퓨터로 나아가는 그래프 탐색 문제
  

• 이미 감염된 경우는, 재감염이 불가능하므로
  ‘시간’이 짧은 쪽으로 맞추어짐
  

• 따라서 priority_queue를 통해
  ‘시간’이 짧은 순으로 큐에서 꺼내
  컴퓨터를 감염시켜나가며
  최종 개수와 시간을 구할 수 있음
  

제출 코드

#include<iostream>
#include<vector>
#include<queue>
#include<unordered_map>

using namespace std;

typedef pair<int, int> pii;

struct Compare
{
	bool operator()(const pii& a, const pii& b)
	{
		return a.second > b.second;
	}
};

pii VirusWork(unordered_map<int, vector<pair<int, int>>>& um,int n, int c)
{
	pii ret;

	int count = 0;
	int maxTime = 0;

	vector<int> visited(n + 1, -1);

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

	pq.push({ c,0 });

	while (pq.empty() == false)
	{
		int now = pq.top().first;
		int nowC = pq.top().second;
		pq.pop();

		if (visited[now] >= 0)
			continue;

		visited[now] = nowC;
		count++;
		if (nowC > maxTime)
			maxTime = nowC;

		for (pii& p : um[now])
		{
			pq.push({ p.first,p.second + nowC });
		}
	}

	ret.first = count;
	ret.second = maxTime;
	return ret;
}

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

	int t;
	cin >> t;

	while (t > 0)
	{
		t--;

		int n, d, c;
		cin >> n >> d >> c;

		unordered_map<int, vector<pii>> um;

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

		pii ret = VirusWork(um,n, c);

		cout << ret.first << ' ' << ret.second << '\n';
	}

	return 0;
}

결과

처음에는 ‘의존성’이라는 키워드를 보고
‘위상정렬’ 문제로 인식을 하였으나
좀 더 살펴보니
최단거리 탐색으로도 충분히 풀 수 있는 문제였다