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

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

민준이가 1에서 V까지 최단경로로 갈 때, 건우를 데려갈 수 있으면 SAVE HIM, 아닐 경우 GOOD BYE를 출력하는 문제이다.

 

민준이가 1에서 출발해 건우까지 가는 최단 경로와 마산까지 가는 최단 경로의 가중치를 첫번째 다익스트라로 구하고,

건우 위치에서 마산으로 가는 최단 경로의 가중치를 두번째 다익스트라로 구한 뒤,

(1 -> 건우) + (건우 -> 마산)  <= (1 -> 마산) 일 경우는 SAVE, 아닐 경우 굿바이를 출력했다.

 

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];
        int geonWoo = info[2];
        List<List<P18223>> 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 P18223(road[1],road[2]));
            list.get(road[1]).add(new P18223(road[0],road[2]));
        }
        int[] dist1 = new int[nodeCount+1]; // 민준 -> 건우, 마산
        int[] dist2 = new int[nodeCount+1]; // 건우 -> 마산
        Arrays.fill(dist1,Integer.MAX_VALUE);
        Arrays.fill(dist2,Integer.MAX_VALUE);
        dijkstra(dist1,1,list);
        dijkstra(dist2,geonWoo, list);

        if(dist1[geonWoo]+dist2[nodeCount]<=dist1[nodeCount]){
            System.out.println("SAVE HIM");
        }else System.out.println("GOOD BYE");
    }
    static void dijkstra(int[] dist, int startNode, List<List<P18223>> list){
        PriorityQueue<P18223> pq = new PriorityQueue<>();
        dist[startNode] = 0;
        pq.offer(new P18223(startNode));
        while(!pq.isEmpty()){
            P18223 poll = pq.poll();
            int value = poll.to;
            int weight = poll.weight;
            if(dist[value]<weight) continue;
            List<P18223> vList = list.get(value);
            for (int i = 0; i < vList.size(); i++) {
                P18223 road = vList.get(i);
                int to = road.to;
                int cost = road.weight;
                if(dist[to]>weight+cost){
                    P18223 offer = new P18223(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 P18223 implements Comparable<P18223> {
    int to;
    int weight = 0;

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

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