[백준] 1504 특정한 최단 경로 - JAVA

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

1504번: 특정한 최단 경로

 

 

[알고리즘]

• 출발지에서 목적지까지의 최단 경로를 구하는 다익스트라 Dijkstra 
• 1 → v1 → v2 → N / 1 → v2 → v1 → N 의 경로 중 최솟값 반환 
• 경로가 존재하는지 확인하기 위한 flag값(isfirst, issecond)을 사용하여, 만약 둘다 경로가 없다면 -1 반환 

---

 

[설계]

• (1 → v1 → v2 → N) / (1 → v1 → v2 → N) 에서의 모든 경로에 대해 최단거리를 구해야한다.  
• 총 3번의 다익스트라를 실행한다. 
  1. 출발지: 1번 노드 (1 → v1, 1 → v2 의 최단거리) 
  2. 출발지: v1 노드 (v1 → v2, v1 → N의 최단거리) 
  2. 출발지: v2 노드 (v2 → v1, v2 → N의 최단거리) 
• Node 클래스 
  1. 정점, 이동거리 저장 
  2. Comparable 인터페이스를 구현하여 이동거리 오름차순 정렬 
  3. 우선순위큐에 저장, 이동거리가 낮을수록 우선순위 ↑ 

---

 

[구현 과정]

• List<ArrayList<Node>> list : 주어진 N개의 정점의 연결정보를 저장한 리스트 
• int first : (1 → v1 → v2 → N) 경로의 최단거리
• int second :  (1 → v1 → v2 → N) 경로의 최단거리
• boolean isfirst, issecond : 위 두 경로가 존재하는지 여부 (false = 가능한 경로 없음) 
• min_dis[] : 다익스트라 구현에서 출발지에서 각 정점까지의 최단 거리 

 

1. N개의 정점과 E개의 간선 정보를 입력받아 list 에 저장. (양방향이므로 a, b 모두 add) 

 

2. v1 → v2 / v2 → v1 의 경로를 탐색하기 위해 3번의 다익스트라를 실행한다. 

 

3. 다익스트라 

• 출발정점, 0 add  
• 현재 정점에서 이동할 수 있는 정점들을 탐색하며, min_dis 에 저장되어 있는 값 보다 현재 정점을 거쳐가는 거리가 더 짧을 경우 최단 거리를 갱신 
• 갱신한 값 min_dis 에 저장하고, 큐에 add 
• 큐가 빌 때 까지 반복

 

 

4. ( 1, v1, v2 ) 노드를 시작점으로 하여 3번의 다익스트라를 실행 한후, first / second 경로의 최단거리를 구한다.

 

5. 가능한 경로가 있는지 (flag 값 isfirst/ issecond)를 고려하여 최솟값을 출력. 

 

---

 

[소스 코드]

import java.util.*;
import java.io.*;

public class Main {
	static List<ArrayList<Node>> list = new ArrayList<>();
	static int N; 
	static class Node implements Comparable<Node>{
		int node;
		int weight;
		
		public Node(int node, int weight) {
			this.node=node;
			this.weight=weight; 
		}

		@Override
		public int compareTo(Node o) {
			return this.weight- o.weight; 
		}
	}
    
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine(), " "); 
		N = Integer.parseInt(st.nextToken()); 
		int E = Integer.parseInt(st.nextToken()); 
		
		for(int i=0; i<=N; i++) {
			list.add(new ArrayList<>()); 
		}
		
		while(E-- >0) {
			st= new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken()); 
			int b = Integer.parseInt(st.nextToken()); 
			int c = Integer.parseInt(st.nextToken()); 
			
			//양방향 저장 
			list.get(a).add(new Node(b,c)); 
			list.get(b).add(new Node(a,c)); 
			
		}
		
		st= new StringTokenizer(br.readLine(), " ");
		
		int v1= Integer.parseInt(st.nextToken());
		int v2= Integer.parseInt(st.nextToken());
		
		
		int first= 0; //v1 - v2 순
		int second = 0; //v2 -v1 순 
		
		boolean isfirst= true; //v1 -v2 경로 있는지 
		boolean issecond = true; //v2 - v1 경로 있는지 
		
		// 1->v1, 1->v2 경로의 최단거리 
		int[] start = dijkstra(1);
		if(start[v1] == Integer.MAX_VALUE) isfirst = false; 
		else first += start[v1]; 
		
		if(start[v2] == Integer.MAX_VALUE) issecond = false; 
		else second += start[v2]; 
		
		// v1-> v2, v1->N 경로의 최단거리 
		int[] v1_arr= dijkstra(v1); 
		if(v1_arr[v2] == Integer.MAX_VALUE) isfirst = false;
		else first += v1_arr[v2]; 
		
		if(v1_arr[N] == Integer.MAX_VALUE) issecond = false;
		else second += v1_arr[N]; 
		
		// v2-> v1, v2-> N 경로의 최단거리
		int[] v2_arr = dijkstra(v2);
		if(v2_arr[v1]== Integer.MAX_VALUE) issecond = false;
		else second += v2_arr[v1]; 
		
		if(v2_arr[N] == Integer.MAX_VALUE) isfirst= false;
		else first += v2_arr[N]; 
		
		
		if(!isfirst && !issecond) System.out.println(-1);
		else {
			if(!isfirst) first= Integer.MAX_VALUE;
			if(!issecond) second = Integer.MAX_VALUE;
			
			System.out.println(Math.min(first, second));
			
		}
 		
	}//end of main 
	
	static int[] dijkstra(int n) {
		PriorityQueue<Node> que= new PriorityQueue<>();
		int[] min_dis = new int[N+1]; 
		Arrays.fill(min_dis, Integer.MAX_VALUE);
		
		que.add(new Node(n,0));
		min_dis[n]=0; 
		
		while(!que.isEmpty()) {
			Node no = que.poll();
			int node= no.node;
			int weight = no.weight;
			
			for(Node next : list.get(node)) {
				int nnode = next.node;
				int nweight= next.weight;
				
				if(min_dis[nnode] > weight + nweight) {
					min_dis[nnode] = min_dis[node]+nweight;
					que.add(new Node(nnode, min_dis[nnode])); 
				}
			}
		}
		
		return min_dis; 
		
	}
}//end of class