백준 1504 특별한 최단 경로 [자바]

09 May 2022 in Develop / Solving

baekjoon 1504 특별한 최단 경로

java

문제 분석

• 방향성 없는 그래프
• 1에서 N까지 이동하는 최단경로를 찾을건데,
• 임의의 두 정점을 반드시 통과하는 최단경로.
• 한번 이동했던 정점, 간선 모두 다시 이용할 수 있음

입력조건

정점의 수 N, 간선의 수 E
E개의 줄에 걸쳐{
	시작점 a, 끝점 b, 가중치 c
}
반드시 거쳐야 하는 두 정점 v1, v2

풀이과정

• 다익스트라
• v1과 v2사이의 거리는 일정하므로
• 답은 (1-v1 거리) + (v2-N 거리) + (v1-v2 거리)이거나, (1-v2 거리) + (v1-N 거리) + (v1-v2 거리) 중 하나.

코드 구성

v1에서 모든 노드로 가는 최단거리를 구하고,

v2에서 모든 노드로 가는 최단거리를 구함.

• 평범하게 다익스트라 코드

public static void dijkstra(int[] from, int v) {
    PriorityQueue<node> pq = new PriorityQueue<>();
    pq.add(new node(v, 0));

    while(!pq.isEmpty()) {
        node a = pq.poll();
        if(from[a.v] < 8000000) continue;
        from[a.v] = a.w; 

        for(node nd : grp[a.v]) {
            if(from[nd.v] < 8000000) continue;
            pq.add(new node(nd.v, nd.w + a.w));
        }
    }
}

• 위 코드를 두 번 돌려서 각 위치로 가는 최솟값을 구한 다음, 가능한 두 개의 답 후보를 비교함.

int set1 = fromv1[1] + fromv2[N];
int set2 = fromv1[N] + fromv2[1];
int ans = Math.min(set1, set2) + fromv1[v2];
System.out.println(ans < 8000000 ? ans : -1 );

전체 코드

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 BJ1504_특정한최단경로 {
	public static class node implements Comparable<node> {
		int v, w;
		node(int v, int w){
			this.v = v;
			this.w = w;
		}
		@Override
		public int compareTo(node o) {
			return this.w - o.w;
		}
	}
	static ArrayList<node>[] grp;
	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());
		grp = new ArrayList[N+1];
		for(int i = 1; i <= N; i++) grp[i] = new ArrayList<>();
		for(int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			grp[u].add(new node(v, w));
			grp[v].add(new node(u, w));
		}
		st = new StringTokenizer(br.readLine());
		int v1 = Integer.parseInt(st.nextToken());
		int v2 = Integer.parseInt(st.nextToken());
		// 입결받기 끝.

		int[] fromv1 = new int[N+1]; Arrays.fill(fromv1, 8000000);
		int[] fromv2 = new int[N+1]; Arrays.fill(fromv2, 8000000);
		dijkstra(fromv1, v1);
		dijkstra(fromv2, v2);
		
		int set1 = fromv1[1] + fromv2[N];
		int set2 = fromv1[N] + fromv2[1];
		int ans = Math.min(set1, set2) + fromv1[v2];
		System.out.println(ans < 8000000 ? ans : -1 );
	}
	public static void dijkstra(int[] from, int v) {
		PriorityQueue<node> pq = new PriorityQueue<>();
		pq.add(new node(v, 0));
		
		while(!pq.isEmpty()) {
			node a = pq.poll();
			// 방문한 적이 있으면 지나가기.
			if(from[a.v] < 8000000) continue;
			// 방문처리
			from[a.v] = a.w; 
			
			for(node nd : grp[a.v]) {
				if(from[nd.v] < 8000000) continue;
				pq.add(new node(nd.v, nd.w + a.w));
			}
		}
	}
}