[이코테] 전보.java

 문제

- N개의 도시, M개의 간선, 시작도시 C가 주어진다.

- X, Y, Z로 간선 정보(X -> Y, Z는 무게)가 주어진다.

- 시작도시 C에서 갈 수 있는 모든 도시의 개수와 최대 걸리는 시간

 

 

 해설 및 코드

import java.util.Arrays;
import java.util.Scanner;

public class 전보 {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int C = sc.nextInt();
		
		int[][] arr = new int[N+1][N+1];
		int[] D = new int[N+1];
		Arrays.fill(D,  Integer.MAX_VALUE);

		for (int i = 0; i < M; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			int z = sc.nextInt();
			
			arr[x][y] = z;
		}
		
		boolean[] check = new boolean[N+1];
		D[C] = 0;
		for (int i = 1; i < N; i++) {
			int min = Integer.MAX_VALUE;
			int index = -1;
			for(int j=0; j<N+1; j++) {
				if(!check[j] && min > D[j]) {
					min = D[j];
					index = j;
				}
			}
			if(index == -1)break;
			for (int j = 1; j < N+1; j++) {
				if(!check[j] && arr[index][j] != 0 && D[index] + arr[index][j] < D[j])
					D[j] = D[index] + arr[index][j];
			}
			check[index] = true;
			
		}
		
		int cnt = 0;
		int max = 0;
		for (int i = 1; i < D.length; i++) {
			if(D[i] != Integer.MAX_VALUE) {
				cnt++;
				max = Math.max(D[i], max);
			}
		}
		
		System.out.println(cnt-1 + " " + max);
		
	}
}

- 다익스트라를 조금만 변형하면 풀 수 있는 문제

- PriorityQueue를 이용한 다익스트라로도 가능하지만, 아직 PirorityQueue는 조금 어색하다.

- 다익스트라 쓰는 법 외우기