백준 10282 (해킹) | 다익스트라 알고리즘(Dijkstra Algorithm)

문제

---

최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.

최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오.

 

 

 

 

 

풀이

---

다익스트라 최단거리 알고리즘을 사용해서 풀었다.

 

· 이 문제에서 주의할 점

a 가 b에 의존하면 b가 감염되면 a 가 감염되는 방향성을 가지고 있다. 

따라서, 입력이 2 1 5 라면 1번 컴퓨터가 2번 컴퓨터에 의존하는 것이므로 1 -> 2 로 방향을 정해서 그래프를 그려야 답을 얻을 수 있다.

 

문제 풀다가 Integer.MAX_VALUE 를 dist 배열의 기본값으로 두었기 때문에, 기준점의 dist 배열값이 Integer.MAX_VALUE 라면 1이라도 더해지면 음수값이 된다. 이점을 막기위해 기준점의 Integer.MAX_VALUE 인지를 판단하는 코드를 넣었다.

if( dist[edge.v].weight != Integer.MAX_VALUE &&(dist[next.v].weight > dist[edge.v].weight + next.weight) )

 

 

<전체코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;

public class Main {	
	
	static class Edge implements Comparable<Edge>{
		int v, weight;
		
		public Edge(int v, int weight) {
			this.v = v;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			// TODO Auto-generated method stub
			
			return Integer.compare(this.weight, o.weight);
		}
	}
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				
		int case_Count = Integer.parseInt(br.readLine());
		
		for(int i = 0 ; i < case_Count ; i++) {
			String[] num = br.readLine().split("\\s");
			
			int n = Integer.parseInt(num[0]);
			int d = Integer.parseInt(num[1]);
			int c = Integer.parseInt(num[2]);
			
			List<Edge>[] list = new ArrayList[n + 1];			
			for(int j = 0 ; j <= n ; j++) {
				list[j] = new ArrayList<>();
			}			
			for(int j = 0 ; j < d ; j++) {
				String[] abw = br.readLine().split("\\s");
				int a = Integer.parseInt(abw[0]);
				int b = Integer.parseInt(abw[1]);
				int w = Integer.parseInt(abw[2]);
				
				list[b].add(new Edge(a, w));
			}
			
			
			//Dijkstar Alorithm start***************************
			PriorityQueue<Edge> pq = new PriorityQueue<>();
			Edge[] dist = new Edge[n + 1];
			
			for(int j = 1 ; j <= n ; j++) {
				//dist 값 초기화
				if( j == c ) {
					dist[j] = new Edge(j, 0);
				}
				else {
					dist[j] = new Edge(j, Integer.MAX_VALUE);
				}
				
				pq.add(dist[j]);
			}
			
			while(!pq.isEmpty()) {
				Edge edge = pq.poll();
				
				for(Edge next : list[edge.v]) {
					if( dist[edge.v].weight != Integer.MAX_VALUE &&(dist[next.v].weight > dist[edge.v].weight + next.weight) ) {
						dist[next.v].weight = dist[edge.v].weight + next.weight;
						
						pq.remove(dist[next.v]);
						pq.add(dist[next.v]);
					}
				}				 
			}
			
			int count = 0, max = 0;
			for(int j = 1 ; j <= n ; j++) {
				if(dist[j].weight != Integer.MAX_VALUE) {
					count++;
					if(dist[j].weight > max) {
						max = dist[j].weight;
					}
				}
			}
			//Dijkstra Algorithm end****************************
			sb.append(count + " " + max).append("\n");
		}		
				
		System.out.println(sb);
	}
}