백준 1238 java - 파티(다익스트라)

문제, 입출력, 테스트케이스

해당 문제는 다익스트라 N번 또는 2번으로 풀 수 있는 문제이다.

<문제 풀이/접근과정>
1. N번 돌리는 경우에는 A -> X로 가는 경우 N-1번, X->A가는 경우 1번 해서 N번 돌리면 된다
2. 2번 돌리는 경우에는 X -> A로 가는 경우 1번과 간선을 반대 방향으로 저장한 간선리스트로 1번 다익스트라를 돌리면 된다.
3. 2번 다익스트라를 돌리는 경우가 가능한 이유는 X에서 다른 노드에 가는 경우는 이해가 되겠지만 간선리스트를 반대방향으로 저장한 경우 특정 노드에서 X로 가는 길이가 바로 A -> X로 가는 경우 N-1번과 동치이기 때문이다.

 

<소스코드>

package 다익스트라;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Boj_1238_파티 {
	static PriorityQueue<int[]> pq;
	static List<int[]>[] v, rv;
	static int dist[], rdist[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(stz.nextToken());
		int M = Integer.parseInt(stz.nextToken());
		int X = Integer.parseInt(stz.nextToken());
		v = new ArrayList[N + 1];
		rv = new ArrayList[N + 1];
		dist = new int[N + 1];
		rdist = new int[N + 1];
		pq = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}

		});
		for (int i = 0; i <= N; i++) {
			v[i] = new ArrayList<int[]>();
			rv[i] = new ArrayList<int[]>();
			dist[i] = 100000000;
			rdist[i] = 100000000;
		}
		for (int i = 0; i < M; i++) {
			stz = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(stz.nextToken());
			int to = Integer.parseInt(stz.nextToken());
			int dist = Integer.parseInt(stz.nextToken());

			v[from].add(new int[] { to, dist });
			rv[to].add(new int[] { from, dist });
		}
		dist[X] = 0;
		rdist[X] = 0;
		
		dijkstra(X);
		
		rDijkstara(X);
		int answer = -1;
		
		for(int i = 1; i <= N;i++) {
			dist[i] += rdist[i];
			answer = Math.max(dist[i], answer);
		}
		System.out.println(answer);
	}

	private static void rDijkstara(int X) {
		pq.add(new int[] { X, 0 });

		while (!pq.isEmpty()) {
			int temp[] = pq.poll();
			int from = temp[0];
			int d = temp[1];

			if (rdist[from] != d)
				continue;

			for (int i = 0; i < rv[from].size(); i++) {
				int nxtNode = rv[from].get(i)[0];
				int nxtD = d + rv[from].get(i)[1];

				if (rdist[nxtNode] > nxtD) {
					rdist[nxtNode] = nxtD;
					pq.add(new int[] {nxtNode, nxtD});
				}
			}

		}

	}

	private static void dijkstra(int X) {
		pq.add(new int[] { X, 0 });

		while (!pq.isEmpty()) {
			int temp[] = pq.poll();
			int from = temp[0];
			int d = temp[1];

			if (dist[from] != d)
				continue;

			for (int i = 0; i < v[from].size(); i++) {
				int nxtNode = v[from].get(i)[0];
				int nxtD = d + v[from].get(i)[1];

				if (dist[nxtNode] > nxtD) {
					dist[nxtNode] = nxtD;
					pq.offer(new int[] {nxtNode, nxtD});
				}
			}

		}
	}
}