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

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

18223번: 민준이와 마산 그리고 건우

 

다익스트라 알고리즘을 활용하여 푼 문제입니다.

 

---

풀이

 

간단한 정리

1 : 시작점

P : 건우가 있는 곳

V : 목적지

1 -> V 까지 가는데 P를 들렸다 가도 최단 거리로 갈 수 있는지 확인하는 문제입니다.

• 기존의 다익스트라 문제와 다르지 않은 방식으로 풀어갔습니다.
• 다만, P를 지나 갔을 때 최단 거리인지 확인하는 로직을 추가했습니다.
• (1 -> P) + (P -> V) <= (1->V) 를 체크할 필요가 있습니다.

 

 

코드

package codingtest.baek18223;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static List<List<Node>> nodes = new ArrayList<>();
    static boolean[] visit;
    static int[] dist;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int V = Integer.parseInt(st.nextToken()); // 정점
        int E = Integer.parseInt(st.nextToken()); // 간선
        int P = Integer.parseInt(st.nextToken()); // 건우의 위치

        visit = new boolean[V+1];
        dist = new int[V+1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        for(int i = 0; i<=V;i++) {
            nodes.add(new ArrayList<>());
        }

        for(int i = 0; i<E; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            nodes.get(start).add(new Node(end,weight));
            nodes.get(end).add(new Node(start, weight));
        }

        dijkstra(1);
        int distV = dist[V];
        int distP = dist[P];

        visit = new boolean[V+1];
        dist = new int[V+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dijkstra(P);

        int pTov = dist[V];

        if(distV == distP + pTov) {
            System.out.println("SAVE HIM");
        } else {
            System.out.println("GOOD BYE");
        }
    }

    private static void dijkstra(int start) {
        PriorityQueue<Node> p = new PriorityQueue<>((o1,o2) -> o1.weight-o2.weight);

        p.add(new Node(start,0));
        dist[start] = 0;

        while (!p.isEmpty()) {
            Node now = p.poll();

            if(!visit[now.x]) {
                visit[now.x] = true;
                List<Node> nextNodes = nodes.get(now.x);
                for(Node n : nextNodes) {
                    if(!visit[n.x] && dist[n.x] > now.weight + n.weight) {
                        dist[n.x] = now.weight + n.weight;
                        p.add(new Node(n.x, now.weight + n.weight));
                    }
                }
            }
        }
    }

    static class Node {
        int x;
        int weight;
        public Node(int x, int weight) {
            this.x = x;
            this.weight = weight;
        }
    }
}