BOJ 18282(해킹) 풀이

solved.ac 난이도 :골드 4

www.acmicpc.net/problem/10282

10282번: 해킹

이문제를 풀려면 지문을 잘 이해해야 된다.

어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.

이 말은 이문제는 단방향 그래프라는 거고 b에서 a로 간다는 말이 된다.

그러므로 입력으로 a, b가 주어졌을 때 다익스트라 코드에 a에서 b가 아닌 b에서 a로 넣는다.

그리고 다익스트라를 하고 각지점마다 최단거리에서 inf가 아닌개수와 inf가 아닌값중에 최댓값을 출력하면 정답이다.