백준 10282. 해킹

해킹

다익스트라 문제 기본 문제

여러 테스트케이스를 다루면서 언제 어떻게 초기화 해야하는지를 알 수 있는 문제

1. 간단 설명

---

최단경로를 풀어봤다면 조금 응용하면 된다

2. 예시

---

2
3 2 2
2 1 5
3 2 5
3 3 1
2 1 2
3 1 8
3 2 4

TC 2개가 주어진다

TC1)

3 2 2 (컴퓨터 3대, 의존성 개수 2개, 해킹당한 컴퓨터 번호 2)

2 1 5 : 2번 컴퓨터는 1번에 의존하며, 5초가 걸림

3 2 5 : 3번이 2번에 의존, 5초 걸림

결과 : 5초 뒤 2, 3 감염된다

TC2)

3 3 1(컴퓨터 3대, 의존성 개수 3개, 해킹 당한 컴퓨터 번호 1)

2->1 2초

3->1 8초

3->2 4초

결과 : 6초 뒤 1,2,3 모두 감염된다

3번은 2번을 거쳐 감염되는게 1번에서 바로 감염되는것보다 빠르다(2초 + 4초 vs 8초)

주의사항

번역이 햇갈릴 수 있는데 그래프 방향에 주의해야한다

a가 b에 의존할 때, s초가 걸린다 b->a (s초)

3. 알고리즘

---

1. TC 개수 입력받기
2. 테스트 케이스가 종료될 때 까지 반복한다
	2-1. 각 테스트케이스별로 n, d, c 입력받기
	2-2. 변수 초기화 진행
	2-3. 바이러스 시작 컴퓨터로부터 다익스트라 수행
	2-4. 다익스트라 종료 후, 감염된 컴퓨터 대수와 최종 시간 확인 후 출력

필요 변수

• 테스트 케이스 개수 int T
• 컴퓨터개수, 의존성 개수, 해킹당한 컴퓨터 번호 int n, d, c (1 ≤ n ≤ 10,000, 1 ≤ d ≤ 100,000, 1 ≤ c ≤ n)
• 의존성 정보 int a, b, s (1 ≤ a, b ≤ n, a ≠ b, 0 ≤ s ≤ 1,000)
• 의존성 정보 맵 vector< vector<pair<int, int» > map;
• 다익스트라 정보
  • 걸린 시간을 기록할 배열 vector<int> d(N+1) 최대 10,000,000이므로 int로 처리 가능
• 감염된 컴퓨터 정보 bool corrupted[N+1]

4. 소스코드

---

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

using namespace std;

int TC;
int n, d, c;
int a, b, s;
vector< vector<pair<int, int>> > map;
vector<int> dist;
vector<bool> corrupted;

void dijkstra(int start) {
	
	dist[start] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push({ start, 0 });
	corrupted[start] = true;

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

		// 현재 노드와 연결된 노드 찾기
		for (int t = 0; t < map[now].size(); t++) {
			int next = map[now][t].first;
			int next_dist = map[now][t].second + now_dist;

			// 구한 경로가 저장된 경로보다 짧다면
			if (next_dist < dist[next]) {
				dist[next] = next_dist;
				corrupted[next] = true;
				pq.push({ next, -next_dist });
			}
		}
	}
}

void Input() {
	cin >> n >> d >> c;

	map.clear();  map.resize(n + 1);
	for (int i = 0; i < d; i++) {
		cin >> a >> b >> s;
		map[b].push_back({ a, s });
	}

	dist.clear(); dist.resize(n + 1);
	for (int i = 0; i <= n; i++) {
		dist[i] = 21e8;
	}

	corrupted.clear(); corrupted.resize(n + 1);
}

void Output() {
	int res = 0, time = 0;
	for (int i = 1; i <= n; i++) {
		if (corrupted[i]) {
			res++;
			if (time < dist[i]) {
				time = dist[i];
			}
		}
	}
	cout << res << ' ' << time << '\n';
}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> TC;

	while (TC--) {
		Input();
		dijkstra(c);
		Output();
	}

	return 0;
}

다익스트라 구현을 위해 연습한 문제

우선순위큐를 사용해서 정렬 시, 음수를 사용해서 최소값을 먼저 뽑아냈다