백준 10282번 해킹

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

10282번: 해킹

 

처음 문제를 보고 그냥 dfs 풀이하면 된다고 생각했다. 왜냐면 그냥 모든 노드를 돌며 시간을 더하면 된다고 봤다. 그러나 이런 케이스를 생각해야한다.

 

1

|       \

2   -    3

 

여기서 1 - 2 는 8초 1 - 3은 2초 2 - 3은 1초라 하자. 그렇다면 1이 감염되었을 때, 2초후 3이 감염되고 3이 감염되고 1초 후 3이 감염되므로 3초면 모두가 감염된다. 그러나 그냥 dfs를 돌아서 2에 먼저 방문할 경우 8초이상이 소모된다고 결과가 나온다. 이것은 잘못된 결과이다. 

 

그래서 이 문제는 다익스트라 알고리즘을 써야한다. 다익스트라를 써야함을 눈치채는 것이 이 문제의 관건이자 실력이라고 본다. 

 

그리고 여기서 정답이 되는 것은 dist 배열의 최대값일 것이다. 난 정답 도출을

 

while (!pq.empty()) {
			int nowNode = pq.top().second;
			answer = dist[nowNode];
			if (visited[nowNode] == false) {
				cnt++;
				visited[nowNode] = true;
			}
			pq.pop();

			for (int j = 0; j < node[nowNode].size(); j++) {
				int nextNode = node[nowNode][j].second;
				int nextValue = node[nowNode][j].first;
				if (dist[nextNode] > dist[nowNode] + nextValue) {
					dist[nextNode] = dist[nowNode] + nextValue;

					pq.push({ -nextValue, nextNode });
				}
			}
		}

 

이런 식으로 정답을 계속 갱신해나가는 식으로 구현했다. 내 논리는 이미 우선순위큐로 정렬되어있고 가장 시간이 적게 걸리는 노드부터 방문할 것이므로 마지막에는 최대값을 방문할 것이라 생각했다. 그러나 마지막으로 방문한 노드가 최대값이라는 보장이 정확하지 않다는 것이 중요했다. 그래서 결국 마지막 dist배열을 모두 검사하는 방식으로 수정하여 AC를 받았다. 그러나 아직까지 안되는 반례는 못찾아서 어떤 반례에서 이것이 불가능한지 모르겠다.

 

#include <iostream>
#include <queue>
#define INF 10484551
using namespace std;

vector<pair<int, int>> node[10001];
int dist[10001];
bool visited[10001];

void init() {
	for (int i = 0; i < 10001; i++) {
		dist[i] = INF;
		node[i].clear();
		visited[i] = false;
	}
}

int main() {
	int T;
	cin >> T;

	for (int i = 0; i < T; i++) {
		init();

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

		for (int j = 0; j < d; j++) {
			int s, e, cost;
			cin >> s >> e >> cost;
			node[e].push_back({ cost, s });
		}

		dist[c] = 0;
		//for (int j = 0; j < node[c].size(); j++) dist[node[c][j].second] = node[c][j].first;

		priority_queue<pair<int, int>> pq;

		pq.push({ 0, c });
		int cnt = 0;
		int answer = INF;
		while (!pq.empty()) {
			int nowNode = pq.top().second;
			answer = dist[nowNode];
			if (visited[nowNode] == false) {
				cnt++;
				visited[nowNode] = true;
			}
			pq.pop();

			for (int j = 0; j < node[nowNode].size(); j++) {
				int nextNode = node[nowNode][j].second;
				int nextValue = node[nowNode][j].first;
				if (dist[nextNode] > dist[nowNode] + nextValue) {
					dist[nextNode] = dist[nowNode] + nextValue;

					pq.push({ -nextValue, nextNode });
				}
			}
		}

		cout << cnt << " " << answer << '\n';
	}
}