[BOJ] 백준 18223. 민준이와 마산 그리고 건우

문제

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

 

 

 

---

풀이

다익스트라를 활용한 문제입니다. 

 

 일반적인 다익스트라 문제와 다른 것은, 특정한 경로를 지나칠 때를 고려해야한다는 것입니다. 특정한 경로를 지나치게하기 위해서 어떤 특별한 장치를 해야하는 것은 아니고, 그 특정 지점에서 다익스트라 알고리즘을 통해 각각의 노드까지의 최단 거리를 구해주기만 하면 됩니다.

 

 그리고 그렇게 구한 최단 거리 배열을 통해 정답을 구할 수 있습니다. 아래는 소스 코드입니다.

 

---

소스 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class B18223_민준이와마산그리고건우 {

    static int V,E,P;
    static int[] dist;
    static int INF = Integer.MAX_VALUE;
    static class Node implements Comparable<Node>{
        int v;
        int w;
        Node(int v, int w){
            this.v=v;
            this.w=w;
        }
        @Override
        public int compareTo(Node o){
            return w-o.w;
        }
    }
    static ArrayList<Node>[] list;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        V = sc.nextInt();
        E = sc.nextInt();
        P = sc.nextInt();
        dist = new int[V+1];
        list = new ArrayList[V+1];
        for(int i = 0;i<V+1;i++){
            list[i] = new ArrayList<>();
        }
        for(int i = 0;i<E;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            list[a].add(new Node(b,c));
            list[b].add(new Node(a,c));
        }

        Arrays.fill(dist,INF);
        dijkstra(1);

        int gunwoo = dist[P];
        int masan = dist[V];

        Arrays.fill(dist,INF);
        dijkstra(P);
        gunwoo += dist[V];

        if(gunwoo<=masan) System.out.println("SAVE HIM");
        else System.out.println("GOOD BYE");
    }
    
    static void dijkstra(int st){
        PriorityQueue<Node> queue = new PriorityQueue<>();
        dist[st] = 0;
        queue.add(new Node(st,0));
        while(!queue.isEmpty()){
            Node now = queue.poll();
            int v = now.v;
            int w = now.w;
            if(dist[v]<w) continue;
            for(Node next:list[v]){
                if(dist[next.v]>w+next.w){
                    dist[next.v] = w+next.w;
                    queue.add(new Node(next.v,w+next.w));
                }
            }
        }
    }
}