[백준BOJ] 1504번 특정한 최단 경로.java

 

백준 저지에서 특정한 최단 경로를 자바를 통해 풀어 보았다. 

 

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

1504번: 특정한 최단 경로

 

1504번 특정한 최단 경로.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

 

1504번 특정한 최단 경로

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.
세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

설명

최단 경로 문제인데 가중치에 음수가 없다면 뒤도 돌아보지말고 다익스트라이다. 단 이 문제에서는 두 정점을 반드시 거쳐야한다. 

 

두 정점을 각각 v1, v2라고 한다면 1번 정점부터 N번 정점까지 가능 경로는 두 가지이다.

1. 1 → v1 → v2 → N

2. 1 → v2 → v1 → N

각 경로에 대해서 최단 경로의 값을 다익스트라를 세 번 써서 구할 수 있다. 예를 들어 첫 번째 경로의 경우 dijkstra(1→v1) + dijkstra(v1→v2) + dijkstra(v2→N)이다. 이렇게 두 경로의 최단 경로를 구하고 비교하여 더 작은 값으로 출력한다. 

 

단 v1, v2를 지나 N번 정점으로 가는 경로가 없을 경우 -1을 출력해야한다. 

코드

//1504번 특정한 최단 경로.java
package week7;

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

public class 특정한_최단_경로_1504 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static class edge{
    	int dest;
    	int distance;
    	edge(int dest, int distance){
    		this.dest = dest;
    		this.distance = distance;
    	}
    }
    static class pre implements Comparable<pre>{
    	int distance;
    	int start;
    	boolean[] point = new boolean[N+1];
    	pre(int distance, int start) {
    		this.distance = distance;
    		this.start = start;
    	}
    	
    	
    	@Override
    	public int compareTo(pre o) {
    		return Integer.compare(this.distance, o.distance);
    	}
    }
    static int N;
    static ArrayList<ArrayList<edge>> Graph;
    static int[] v ;
    public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		
		Graph = new ArrayList<ArrayList<edge>>();
		for(int i=0;i<=N;i++) {
			Graph.add(new ArrayList<edge>());
		}
		for(int i=0;i<E;i++) {
			st = new StringTokenizer(br.readLine()," ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			Graph.get(a).add(new edge(b,c));
			Graph.get(b).add(new edge(a,c));
		}
		v = new int[2];
		st = new StringTokenizer(br.readLine()," ");
		v[0] = Integer.parseInt(st.nextToken());
		v[1] = Integer.parseInt(st.nextToken());
		int result1 = dijkstra(1,v[0]) + dijkstra(v[0],v[1]) + dijkstra(v[1],N);
		int result2 = dijkstra(1,v[1]) + dijkstra(v[1],v[0]) + dijkstra(v[0],N);
		int answer = Math.min(result1, result2);
		if(answer<0 || answer == 2147483645)answer=-1;
		System.out.println(answer);
		
	}
    public static int dijkstra(int start, int dest) {
    	int[] root = new int[N+1];
    	Arrays.fill(root, Integer.MAX_VALUE);
    	root[start] = 0;
    	PriorityQueue<pre> minHeap = new PriorityQueue<>();
    	minHeap.add(new pre(0,start));
    	
    	while(!minHeap.isEmpty()) {
    		pre now = minHeap.poll();
    		if(root[now.start] < now.distance)continue;
    		
    		for(edge next : Graph.get(now.start)) {
    			int nextCost = now.distance+next.distance;
    			if(nextCost < root[next.dest]) {
    				root[next.dest] = nextCost;
    				minHeap.add(new pre(nextCost, next.dest));
    			}
    		}
    	}
    	return root[dest];
    }
}