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

 

 

 

최단 거리 문제이다. 

최단 거리 문제는 보통 BFS를 통해서 구할 수 있는데 BFS를 이용하면 DFS보다 그래프의
level 단위로 검사하기 때문에 일반적으로 더 빠르고 안정적으로 최단거리를 구할 수 있다. 

이떄 가중치가 존재한다면 다익스트라, 벨만포드, 플로이드중 하나를 사용해야하는데 
이 문제는 시작점이 3개로 고정이고, 음수 사이클이 존재하지 않기 때문에 
다익스트라를 통해서 구현하면 된다.

 

문제 설명 

1에서 N까지 움직이는데 경유점 c1, c2를 반드시 거쳐서 도달해야한다
그럼 총 2가지 경우의 수가 나올 것이다 
1 -> c1 -> c2 -> N

1 -> c2 -> c1 -> N 

1에서 시작하는 최단거리 

c1에서 시작하는 최단거리 
c2 에서 시작하는 최단 거리를 구한후 

2가지 경우에 대해 MAX 값을 처리하면 된다.

 

이때 방향없는 그래프라는 점을 잘 보자.. 문제를 잘 읽어야 시간을 아낄 수 있다.. 

 

package 백준;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class 특정한최단경로1504 {

    public static class Pair{
        int loc;
        int w;

        Pair(int loc, int w){
            this.loc = loc;
            this.w = w;
        }

        int getW(){
            return w;
        }
    }

   static int v;
   static ArrayList<ArrayList<Pair>> adj;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw =new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");

        v = Integer.parseInt(input[0]);
        int e = Integer.parseInt(input[1]);
        adj = new ArrayList<>();
        for(int i =0; i<=v; i++){
            adj.add(new ArrayList<>());
        }

        for(int i =0; i<e; i++){
            String[] vInput = br.readLine().split(" ");

            int src = Integer.parseInt(vInput[0]);
            int des = Integer.parseInt(vInput[1]);
            int w = Integer.parseInt(vInput[2]);
            adj.get(src).add(new Pair(des,w));
            adj.get(des).add(new Pair(src,w));
        }
        String[] c = br.readLine().split(" ");

        int c1 = Integer.parseInt(c[0]);
        int c2 = Integer.parseInt(c[1]);

        int[] src1 = dijkstra(1);
        int[] srcc1 = dijkstra(c1);
        int[] srcc2 = dijkstra(c2);

        int answer =
                Math.min(src1[c1] + srcc1[c2] + srcc2[v], src1[c2]+ srcc2[c1] + srcc1[v]);
        if(answer > ((Integer.MAX_VALUE-30)/3 -1 ) ) answer = -1;
        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }

    public static int[] dijkstra(int src){
        int[] dist = new int[v+1];

        Arrays.fill(dist,(Integer.MAX_VALUE-30) /3);
        dist[src] = 0;


        PriorityQueue<Pair> pq = new PriorityQueue<>(Comparator.comparing(Pair::getW));

        pq.offer(new Pair(src, 0));

        while(!pq.isEmpty()){
            Pair current = pq.poll();
            int here = current.loc;
            int cost = current.w;
            if( cost> dist[here]) continue;
            dist[here] = cost;

            for(Pair p : adj.get(here)){
                int there = p.loc;
                int thereCost = p.w;

                if(dist[here] + thereCost < dist[there]){
                    pq.offer(new Pair(there, dist[here]+ thereCost));
                }
            }
        }
        return dist;

    }
}

 

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