백준 1504 java - 특정한 최단 경로(최적화된 다익스트라)

문제, 입출력, 테스트코드

해당 문제는 다익스트라를 이용한 문제로 다익스트라를 까먹고 다시 공부해서 풀게 된 문제이다.

 

 

<문제 풀이/접근과정>
1. 정점의 개수 N(2 ≤ N ≤ 800), 간선의 개수 E(0 ≤ E ≤ 200,000), 거리 c (1 ≤ c ≤ 1,000)
2. 다익스트라를 3번 돌리면 된다. (1에서 한 번, v1에서 한 번, v2에서 한 번)
3. 최적화된 다익스트라 기준 시간 복잡도 O(logN*(N+M)) = O((N+M)logN)(N은 정점 수 , M은 간선 수) -> 3번 돌리므로 3*O((N+M)logN)
4. distance의 INF값은 무지성 Integer.MAX_VALUE를 쓰기보다 정확한 계산을 근거로 넣어야 하므로 싸이클 다 돈다고 생각하면 800 x 1000 이므로 800,000보다 큰 값을 INF값으로 대체해서 사용하면 된다. -> 넉넉하게 900,000지정
5. 그리고 경로가 없을 떄에는 -1 출력하므로 경로 유무에 따라 정답값을 출력하면 된다.

package boj;

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

public class Boj_1504 {
	static class Node implements Comparable<Node> {
		int num;
		int distance;

		public Node(int num, int distance) {
			super();
			this.num = num;
			this.distance = distance;
		}

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

	}

	static int N, E, dist[], v[][], first, second;
	static PriorityQueue<Node> pq;

	public static void main(String[] args) throws IOException {

		// 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000)
		// 다익스트라 세번 1, v1, v2에서 각각 돌린 후 1->v1 + v1-> v2 + v2 -> N / 1-> v2 + v2 -> f1 +
		// v1-> N 더한 거에서 최솟값 구하고 한 곳이라도 방문 못한다면 -1출력
		// 최적화된 다익스트라

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz;
		stz = new StringTokenizer(br.readLine());
		N = Integer.parseInt(stz.nextToken());
		E = Integer.parseInt(stz.nextToken());

		v = new int[N + 1][N + 1];
		pq = new PriorityQueue<>();

		// 간선 정보 받기
		for (int i = 0; i < E; i++) {
			stz = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(stz.nextToken());
			int to = Integer.parseInt(stz.nextToken());
			int weight = Integer.parseInt(stz.nextToken());
			v[from][to] = weight;
			v[to][from] = weight;
		}
		stz = new StringTokenizer(br.readLine());
		first = Integer.parseInt(stz.nextToken());
		second = Integer.parseInt(stz.nextToken());

		int dist1[] = dijkstra(1);
		int dist2[] = dijkstra(first);
		int dist3[] = dijkstra(second);
		int preAnswer1 = dist1[first] == 900000 || dist2[second] == 900000 || dist3[N] == 900000 ? -1: dist1[first] + dist2[second] + dist3[N];
		int preAnswer2 = dist1[second] == 900000 || dist3[first] == 900000 || dist2[N] == 900000 ? -1 : dist1[second] + dist2[N] + dist3[first];
		if (preAnswer1 != -1 && preAnswer2 != -1) {
			System.out.println((int) Math.min(preAnswer1, preAnswer2));
		} else if (preAnswer1 == -1 && preAnswer2 == -1) {
			System.out.println(-1);
		} else {
			System.out.println((int) Math.max(preAnswer1, preAnswer2));
		}

	}

	private static int[] dijkstra(int j) {
		int dist[] = new int[N + 1];

		for (int i = 1; i < dist.length; i++) {
			if (i == j) {
				dist[i] = 0;
				pq.offer(new Node(i, dist[i]));
			} else {
				dist[i] = 900000;
				pq.offer(new Node(i, dist[i]));
			}
		}

		while (!pq.isEmpty()) {// pq 다 사라질 때 까지 고르기
			// 1. 가장 작은 distance 노드 고르기
			Node temp = pq.poll();
			int cur = temp.num;
			int distance = temp.distance;
			if (dist[cur] != distance)
				continue;
			// 3. 해당 노드에서 간선 다 돌면서 최솟값 갱신
			for (int i = 1; i < v[cur].length; i++) {
				if(v[cur][i] == 0 )continue;
				int tempdist = v[cur][i] + dist[cur];
				if (tempdist < dist[i]) {
					dist[i] = tempdist;
					pq.offer(new Node(i, dist[i]));
				}
			}
		}

		return dist;
	}

}

다익스트라를 모르면 못 푸는 문제이다.