[백준] 1238번: 파티 - java

 

아이디어

V = 정점의 갯수

E = 간선의 갯수 

T = 목적지 (파티가 열리는 곳)

라고 할 때 다익스트라를 V번 반복하지 않아도 이 문제를 풀 수 있다.

 

1) T를 출발 노드로 하여 다익스트라 알고리즘을 돌린다.

=> T에서 출발해서 다른 노드로 가는 최단경로를 모두 구한다.

 

그럼 이제 임의의 노드 x에서 출발해서 T로 오는 거리만 찾으면 답을 구할 수 있다.

2) x -> T 거리를 구하기 위해선 출발노드 x가 매번 다르기 때문에 다익스트라를 n번 반복해야 한다.

하지만 그래프 간선방향을 거꾸로 뒤집고, (1->3 을 3->1 으로 변경)   

T 노드를 출발 노드로 하여 다익스트라를 돌리면 x -> T 의 거리를 모두 구할 수 있다.

 

3) 1, 2 에서 구한 거리를 더해서 가장 큰 값을 찾는다!

 

이렇게 O(|E| + |V| log |V|) 만에 문제를 풀 수 있다.

플로이드 워셜은 O(|V|^3) 이기 때문에 이번 문제에서는 사용하지 않았다.

 

 

 

코드설명

파티가 열리는 정점이 X라고 하면 adj 일 때 X로 들어오는 모든 간선은 

reverse_arrList에서는 X에서 나가는 간선이 된다.

 

다익스트라 알고리즘은 하나의 정점에서 모든 정점으로 도달하는 최단 거리를 구하는 알고리즘이므로

X를 시작지점으로 두고 adj에서 최단 거리를 구하면 X~모든정점으로, 파티가 끝나고 집으로 돌아가는 최단 거리 이다.

X를 시작지점으로 두고 r_adj에서 최단거리를 구하면 각 사람들이 파티에 모이기 위한 최단거리가 된다.

 

 

 

위의 그림을 보자. 보통 다익스트라 최단경로 문제에서는 1번에서 출발하여 i번까지 가려고 할 때 소모되는 비용이나 경로를 출력하라고 한다. 그러면 보통 1번 정점에서 시작하여 우선순위 큐를 통해 그래프 전체를 확인하고 마무리한다.

그런 후에 i번 정점에 담긴 비용을 확인하여 답을 구한다.

여기서 우리는 사실 1번에서i번까지 가는 최단경로만 구한 게 아니라, 1번에서 출발하여 다른 모든 정점에 대한 최단경로를 구한 것이다. 단지 그중에 i번 도착점 값만 확인했을 뿐이었다. 

여기서 중요한 것은 출발점이 주어지면 그래프내의 모든 정점에 대한 최단경로가 단 한 번의 다익스트라 연산을 통해 구해진다는 점이다.

 

 

 

 

이 문제에서는 출발점이 아니라 도착점이 주어진다. 모든 정점에서 그 도착점에 다다르기 위한 최단경로를 구해야 한다. 그렇다면 모든 정점에서 매번 다익스트라를 돌려야 할까?

여기서 역방향 그래프가 등장한다!

위의 그래프는 원래 그래프에서 간선만 반대방향으로 뒤집은 것이다.

간선 방향을 뒤집어서 최단경로를 구했지만, 원래 그래프에서도 각 정점이 6번 도착점에 오기 위해서는 같은 경로를 선택해야 한다는 것을. 이렇게 역방향 그래프를 사용하면, 단 한번의 다익스트라 연산을 통해 각 정점에서 6번 도착점에 이르기 위한 최단경로 비용을 모두 구할 수 있다.

 

처음에 입력받을 때, 역방향 그래프도 같이 만들어주면 된다.

 

 

나의코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringBuilder sb;
	static StringTokenizer st;
	static int n, m, x, a, b, t, dist[], r_dist[];
	static ArrayList<Node> adj[], r_adj[];

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

		adj = new ArrayList[n + 1];
		r_adj = new ArrayList[n + 1];
		dist = new int[n+1];
		r_dist = new int[n+1];
		Arrays.fill(dist, Integer.MAX_VALUE);
		Arrays.fill(r_dist, Integer.MAX_VALUE);

		for (int i = 0; i <= n; i++) {
			adj[i] = new ArrayList<>();
			r_adj[i] = new ArrayList<>();
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			t = Integer.parseInt(st.nextToken());
			adj[a].add(new Node(b, t));
			r_adj[b].add(new Node(a, t));
		}

		// i~x 구하기
		dijkstra(adj, dist, x);
		
		// x~i 구하기
		dijkstra(r_adj, r_dist, x);
		
		// i~x + x~i 중 최댓값 구하기
		int max = 0;
		for(int i=1; i<=n; i++) {
			max = Math.max(max, dist[i] + r_dist[i]);
		}
		
		System.out.println(max);

	}

	static void dijkstra(ArrayList<Node>[] arr, int[] dist, int start) {
		PriorityQueue<Node> q = new PriorityQueue<Node>();
		q.add(new Node(start, 0));
		dist[start] = 0;
		
		while(!q.isEmpty()) {
			Node now = q.poll();
			for(Node next : arr[now.node]) {
				if (dist[next.node] > dist[now.node] + next.time) {
					dist[next.node] = dist[now.node] + next.time;
					q.add(new Node(next.node, dist[next.node]));
				}
			}
		}
	}

	static class Node implements Comparable<Node> {
		int node;
		int time;

		public Node(int node, int time) {
			super();
			this.node = node;
			this.time = time;
		}

		@Override
		public int compareTo(Node o) {
			return this.time - o.time;
		}

	}

}