[Java] 백준 / 특정한 최단 경로 / 1504

[Java] 백준 / 특정한 최단 경로 / 1504

문제

문제 링크

접근 방식

1번 점에서 부터 v1 , v2 를 거쳐 N번 점으로 이동할 경우의 수는 총 두 가지이다

따라서 이 두 가지에 대해 최단 경로를 구한다

1. 1번 점 → v1 , v1 → v2, v2→ N 에 대해 각각 다익스트라 알고리즘으로 최단거리를 구하여 더한다
2. 위와 같이 1번 점 → v2, v2 -> v1, v1 → N에 대한 최단거리를 구한 후 위와 비교하여 더 짧은 경로를 출력한다
3. 각각의 경로를 탐색하는 도중에 경로가 없을 시에 대한 조건을 추가한다

코드

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 Main_1504 {

	public static class Vertex implements Comparable<Vertex>{
		int no;
		int w;
		
		Vertex(int no, int w){
			super();
			this.no  = no;
			this.w = w;
		}
		
		@Override
		public int compareTo(Vertex o) {
			return this.w - o.w;
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		
		ArrayList<ArrayList<Vertex>> list = new ArrayList<>();
		
		for(int i=0;i<=N;i++) {
			list.add(new ArrayList<>());
		}
		
		for(int i=0;i<E;i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			list.get(v1).add(new Vertex(v2,w));
			list.get(v2).add(new Vertex(v1,w));
			
		}
		
		st = new StringTokenizer(br.readLine());
		int n1 = Integer.parseInt(st.nextToken());
		int n2 = Integer.parseInt(st.nextToken());
		
		int[][] numLists = {{1,n1,n2,N},{1,n2,n1,N}};
		
		int minDistance = Integer.MAX_VALUE;
		boolean hasNotPath = false;
		loop : for(int[] numList : numLists) {
			int d = 0;
			for(int i=0;i<3;i++) {
				int start = numList[i];
				int end = numList[i+1];
				
				int[] distance = new int[N+1];
				Arrays.fill(distance, Integer.MAX_VALUE);
				
				boolean[] visited = new boolean[N+1];
				
				distance[start] = 0;
				
				PriorityQueue<Vertex> pq = new PriorityQueue<>();
				pq.offer(new Vertex(start, distance[start]));
				
				while(!pq.isEmpty()) {
					int current = pq.poll().no;
					
					if(visited[current]) continue;
					
					if(current == end) {
						break;
					}
					
					for(Vertex v : list.get(current)) {
						if(distance[v.no] > distance[current] + v.w ) {
							distance[v.no] = distance[current] + v.w;
							pq.offer(new Vertex(v.no,distance[v.no]));
						}
					}
				}
				
				if(distance[end] != Integer.MAX_VALUE) {
					d += distance[end];
				}
				else {
					hasNotPath = true;
					continue loop;
				}
			}
			
			minDistance = Math.min(minDistance, d);
		}
		
		if(hasNotPath) System.out.println(-1);
		else System.out.println(minDistance);
		
		
	}

}