백준 | 1238번. 파티 - 다익스트라 문풀

⬛ 백준 1238번. 파티 - 다익스트라 문풀

• 다익스트라 : one - to - All : 한 정점에서 다른 든 정점에 대한 최단거리

https://www.acmicpc.net/problem/1238

1238번: 파티

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

💚나의 풀이

• 처음에는 가는 방식과 돌아오는 방식을 플로이드로 풀어야 하나 싶었는데, (돌아오는 정점이 여러개니까). 근데 그건 시간 초과가 뜰 것 같았다.
• 다익스트라 : ‘한 정점에서 다르 모든 정점으로의 최단거리’ 라는 것을 생각하자.
• 그래프를 2개 준비한다.정방향과 역방향.
• 그리고 똑같이 출발점 X에서 다르 모든 정점으로의 최단거리를 구하게 되면 정방향 그래프에서는 X로의 최단 거리가 되고, 역방향에서는 X에서의 최단 거리가 된다.
• 이런 식으로 알고리즘의 정의와 문제 매칭을 제대로 하는 것이 필요하겠다고 생각했다.

package to_0831_1;

import java.util.*;
import java.util.PriorityQueue;
import java.util.Scanner;

/*1238번. 파티 - 다익스트라 문풀 */
class Edge implements Comparable<Edge>{
	int e, val;
	Edge(int e, int val){
		this.e =e;
		this.val =val;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.val - o.val;
	}
}
public class Main {
	static int N, M, X;
	static int[] dist1;//가는 길
	static int[] dist2;//돌아오는 길 
	static ArrayList<ArrayList<Edge>> A;//정방향 
	static ArrayList<ArrayList<Edge>> B;//역방향 
	
	//다익스트라 함수 
	static int[] dijkstra(ArrayList<ArrayList<Edge>> graph) {
		int[] dist = new int[N+1];	
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		//다익스트라는 무한대 초기화
		Arrays.fill(dist, Integer.MAX_VALUE);
		//시작점 초기화
		dist[X] = 0;
		pQ.offer(new Edge(X, 0));//X로 향하는 길이 0
		
		while(!pQ.isEmpty()) {
			Edge cur = pQ.poll();
			int cur_e = cur.e;
			int cur_val= cur.val;
			
			for(Edge nx : graph.get(cur_e)) {
				if(dist[nx.e] > dist[cur_e] + nx.val) {
					dist[nx.e] = dist[cur_e] + nx.val;
					pQ.offer(new Edge(nx.e, dist[nx.e]));
				}
			}
		}
		return dist;
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		N = kb.nextInt();
		M = kb.nextInt();
		X = kb.nextInt();
		
		A = new ArrayList<>();
		B = new ArrayList<>();
		
		//공간 생성 
		for(int i=0; i<=N; i++) {
			A.add(new ArrayList<>());
			B.add(new ArrayList<>());
		}
		
		//데이터 입력 받기 
		for(int i=0; i<M; i++) {
			int s = kb.nextInt();
			int e = kb.nextInt();
			int val =kb.nextInt();
			//정방 역방 
			A.get(s).add(new Edge(e, val));
			B.get(e).add(new Edge(s, val));
		}
		
		dist1 = dijkstra(A);
		dist2 = dijkstra(B);
		
		int max = -1;
		for(int i=1; i<=N; i++) {
			max = Math.max(max, dist1[i]+dist2[i]);
		}
		
		System.out.println(max);
	}
}