[Java] 백준 / 파티 / 1238

[Java] 백준 / 파티 / 1238

문제

문제 링크

접근 방식

각 점에서부터 X점까지의 최단 시간과, 다시 X점에서 각 점으로의 최단시간 합 중 가장 긴 시간을 출력하면 된다

1. X 점에서 각 점까지의 최단시간은 X점을 시작으로 전체 점으로의 최단거리를 구하는 다익스트라 알고리즘을 사용한다
2. 각 점에서 X점 까지의 최단시간은 간선 정보를 반대로 받은 후 다시 X점에서 각 점으로 최단거리를 구하는 것과 같다
3. 따라서 총 두 번의 다익스트라 알고리즘을 사용하여 왕복 시간 중 가장 긴 시간을 출력한다

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_1238 {
	
	static int N,M,X;
	static int maxTime;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		X = Integer.parseInt(st.nextToken());
		
		int [][]adjMatrix = new int[N+1][N+1];
		int [][]adjMatrixRev = new int[N+1][N+1];
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			int t = Integer.parseInt(st.nextToken());
			
			adjMatrix[v1][v2] = t;
			adjMatrixRev[v2][v1] = t;
		}
		
		maxTime = 0;
		
		
		
		int[] d1 = dijkstra(adjMatrix);
		int[] d2 = dijkstra(adjMatrixRev);
		
		for(int i=1;i<=N;i++) {
			maxTime = Math.max(maxTime, d1[i]+d2[i]);
		}
		
		
		System.out.println(maxTime);
	}
	
	
	public static int[] dijkstra(int[][] adjMat) {
		int start = X;
		
		int[] distance = new int[N+1];
		boolean[] visited = new boolean[N+1];
		
		Arrays.fill(distance, Integer.MAX_VALUE);
		distance[start] = 0;
		
		
		for(int i=0;i<N;i++) {
			int current = 0;
			int min = Integer.MAX_VALUE;
			
			for(int j=1;j<=N;j++) {
				if(!visited[j] && distance[j] < min) {
					min = distance[j];
					current = j;
				}
			}
			
			
			visited[current] = true;
			
			
			for(int j=1;j<=N;j++) {
				if(!visited[j] && adjMat[current][j] != 0 &&  distance[j] > distance[current] + adjMat[current][j]) {
					distance[j] = distance[current] + adjMat[current][j];
					
				}
				
			}
		}
		
		return distance;
	}
}