[JAVA] 백준 23793 - 두 단계 최단 경로 1

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

 

정점 X,Y,Z를 포함한 N개의 정점이 주어질 때, X->Y->Z 경로의 최단 길이와, X->Z(Y 포함하지 않음)의 최단 길이를 구하는 문제이다.

https://ghcode.tistory.com/300

[JAVA] 백준 18223 - 민준이와 마산 그리고 건우

민준이가 마산으로 갈 때 건우를 데려갈 수 있는지 여부를 판단하는 문제와 비슷한데, 이번 문제는 Y를 포함하지 않아야 한다는 조건이 추가되었다.

 

총 3번의 다익스트라를 돌리는데, 첫번째는 X->Y를 구하고 두번째는 Y->Z를 구해  X->Y->Z의 길이를 구한다.

마지막 다익스트라를 돌리기 전 간선을 저장하는 Y번째 list를 초기화해 Y에서 outbound로 나가는 간선을 없애고 마지막 다익스트라를 돌려 X -> Z의 길이를 구한다.

Z까지 도달하지 못하는 경우 -1를 출력해야 하는데,  X->Z 한번만 했다가 틀리고, X->Z, Y->Z 두개 했다가 틀리고

마지막으로 X->Y까지 처리해주고 나서야 통과했다. 

미리미리 조건 체크를 꼼꼼하게 하는 습관을 들여야겠다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] info = getArray(br.readLine());
        int nodeCount = info[0];
        int roadCount = info[1];
        List<List<P23793>> list = new ArrayList<>();
        for (int i = 0; i <= nodeCount; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < roadCount; i++) {
            int[] road = getArray(br.readLine());
            list.get(road[0]).add(new P23793(road[1],road[2]));
        }
        info = getArray(br.readLine());
        int startNode = info[0];
        int middleNode = info[1];
        int endNode = info[2];
        int[] dist1 = new int[nodeCount+1];
        int[] dist2 = new int[nodeCount+1];
        int[] dist3 = new int[nodeCount+1];
        Arrays.fill(dist1,Integer.MAX_VALUE);
        Arrays.fill(dist2,Integer.MAX_VALUE);
        Arrays.fill(dist3,Integer.MAX_VALUE);
        dijkstra(dist1,startNode,list);
        dijkstra(dist2,middleNode, list);
        list.set(middleNode,new ArrayList<>());
        dijkstra(dist3,startNode,list);
        int ans = dist2[endNode]==Integer.MAX_VALUE||dist1[middleNode]==Integer.MAX_VALUE?-1:dist1[middleNode]+dist2[endNode];
        System.out.println(ans+" " +(dist3[endNode]==Integer.MAX_VALUE?-1:dist3[endNode]));
    }
    static void dijkstra(int[] dist, int startNode, List<List<P23793>> list){
        PriorityQueue<P23793> pq = new PriorityQueue<>();
        dist[startNode] = 0;
        pq.offer(new P23793(startNode));
        while(!pq.isEmpty()){
            P23793 poll = pq.poll();
            int value = poll.to;
            int weight = poll.weight;
            if(dist[value]<weight) continue;
            List<P23793> vList = list.get(value);
            for (int i = 0; i < vList.size(); i++) {
                P23793 road = vList.get(i);
                int to = road.to;
                int cost = road.weight;
                if(dist[to]>=weight+cost){
                    P23793 offer = new P23793(to);
                    offer.weight = weight+cost;
                    dist[to] = weight+cost;
                    pq.offer(offer);
                }
            }
        }
    }


    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}
class P23793 implements Comparable<P23793> {
    int to;
    int weight = 0;

    P23793(int t){
        this.to = t;
    }
    P23793(int t, int weight) {
        this.to = t;
        this.weight = weight;
    }

    @Override
    public int compareTo(P23793 o) {
        return this.weight - o.weight;
    }
}