[BOJ] [JAVA] 1238번 파티

1238번: 파티

그래프의 정점과 간선이 주어지고 각 정점에서 특정 정점(파티)까지 갔다가 되돌아는 최단거리 중 최댓값을 구하는 문제다.

다익스트라 알고리즘을 활용해서 해결할 수 있었다.

다익스트라는 임의의 시작점에서부터 다른 노드로 가는 최단거리를 구할 수 있는 알고리즘이다.

다이내믹 프로그래밍과 유사하다고 느꼈다. dp의 일종인가?

그래프를 두 가지로 동시에 입력받았다.

하나는 입력 그대로의 그래프 (파티에서 각자의 집으로 돌아갈 때 다익스트라를 적용할 그래프)

다른 하나는 간선을 거꾸로 돌린 그래프(집에서 파티로 가는 경우의 다익스트라를 적용할 그래프)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static List<Edge>[] graph1; // 파티에서 집으로 (기존 그래프)
	static List<Edge>[] graph2; // 집에서 파티로 (간선을 거꾸로 돌린 그래프)

	static int[] dpt;
	static int[] arv;
	static boolean[] visit;
	static PriorityQueue<Edge> pq; // 파티가 시작점인 간선들만 저장되도록 함

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int party = Integer.parseInt(st.nextToken());

		graph1 = new List[n + 1];
		graph2 = new List[n + 1];

		for (int i = 1; i <= n; i++) {
			graph1[i] = new LinkedList<>();
			graph2[i] = new LinkedList<>();
		}

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int time = Integer.parseInt(st.nextToken());

			graph1[start].add(new Edge(end, time));
			graph2[end].add(new Edge(start, time));
		}

		// 파티에서 집까지 가는 최단거리 : graph1 사용
		dpt = new int[n + 1];
		for (int i = 1; i <= n; i++)
			dpt[i] = Integer.MAX_VALUE;
		dpt[party] = 0;
		visit = new boolean[n + 1];
		pq = new PriorityQueue<>();
		pq.offer(new Edge(party, 0));
		departure();

		// 집에서 파티까지 가는 최단거리 : graph2 사용
		arv = new int[n + 1];
		for (int i = 1; i <= n; i++)
			arv[i] = Integer.MAX_VALUE;
		arv[party] = 0;
		visit = new boolean[n + 1];
		pq = new PriorityQueue<>();
		pq.offer(new Edge(party, 0));
		arrival();
		
		int ans = 0;
		
		for (int i = 1; i <= n; i++) {
			int k = dpt[i] + arv[i];
			if (k > ans) ans = k;
		}
		System.out.println(ans);
	}

	static void departure() {
		while (!pq.isEmpty()) {
			Edge e = pq.poll();
			if (visit[e.to])
				continue;
			visit[e.to] = true;

			for (Edge next : graph1[e.to]) {
				if (dpt[next.to] > dpt[e.to] + next.wei) {
					dpt[next.to] = dpt[e.to] + next.wei;
					pq.offer(new Edge(next.to, dpt[next.to]));
				}
			}
		}
	}
	
	static void arrival() {
		while (!pq.isEmpty()) {
			Edge e = pq.poll();
			if (visit[e.to])
				continue;
			visit[e.to] = true;

			for (Edge next : graph2[e.to]) {
				if (arv[next.to] > arv[e.to] + next.wei) {
					arv[next.to] = arv[e.to] + next.wei;
					pq.offer(new Edge(next.to, arv[next.to]));
				}
			}
		}
	}
}

class Edge implements Comparable<Edge> {
	int to;
	int wei;

	public Edge(int to, int wei) {
		this.to = to;
		this.wei = wei;
	}

	@Override
	public int compareTo(Edge o) {
		return this.wei - o.wei;
	}
}