리트코드 leetCode 743.Network Delay Time

문제 : https://leetcode.com/problems/network-delay-time/

Network Delay Time - LeetCode

 

풀이 : 다익스트라 알고리즘 사용

2021.09.19 - [알고리즘/알고리즘] - 다익스트라 알고리즘 Dijkstra's algorithm

 

구현 JAVA

class Solution {

	public int networkDelayTime(int[][] times, int n, int k) {
		
		/** ① 그래프 경로를 배열로 저장 **/
		int[][] vertex = new int[n+1][n+1];
        for(int[] v : vertex) {
			Arrays.fill(v, -1);
		}
		for(int[] time: times) {
			vertex[time[0]][time[1]] =time[2];
		}
		/** ② 최단경로 결과값을 저장할 배열을 선언 **/
		int[] queue = new int[n+1];
		Arrays.fill(queue, Integer.MAX_VALUE);
		/** ③ 시작점 초기화 **/
		boolean[] isVisited = new boolean[n+1]; //방문여부
		queue[k] = 0;
		
		/** ④ 다익스트라 구현**/		
		dijkstra(vertex, queue, isVisited, k, n );
		
		Arrays.sort(queue);
		
		return queue[n-1] == Integer.MAX_VALUE ? -1 : queue[n-1];
	}

	private void dijkstra(int[][] vertex, int[] queue, boolean[] isVisited, int k, int n) {
		
		
		for(int i = 1; i<=n; i++) {
			//현재 경로 중 최소값을 구하기
			int min = findMin(queue, isVisited);
			isVisited[min] = true;
			for(int v = 1; v<=n; v++) {
				//최소값을 거쳐서 v로 가는게 바로 v로 가는 것보다 비용이 적으면 v의 최단경로 값을 업데이트 
				int newRoute = queue[min] + vertex[min][v];
				if(!isVisited[v] && vertex[min][v] != -1 && newRoute < queue[v] ) {
					queue[v] = newRoute;
				}
			}
		}
		
	}

	private int findMin(int[] queue, boolean[] isVisited) {
		
		int minValue = Integer.MAX_VALUE;
		int minIndex = -1;
		for(int i = 1; i<queue.length; i++) {
			if(!isVisited[i] && queue[i]<=minValue) {
				minValue = queue[i];
				minIndex = i;
			}
		}
		return minIndex;
	}
}