BOJ 18223 민준이와 마산 그리고 건우(JAVA) 🚍

문제 링크

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

문제 설명

1~V 정점과 양방향 간선이 주어지고, 1->V 최단 경로에 건우의 위치인 P를 거치면 "SAVE HIM" 을 아니면 "GOOD BYE"을 출력한다.

입력

입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V  ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P  ≤ V)

두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 a,b,c가 공백으로 구분되어 주어진다. 이는 a번 정점과 b번 정점 사이의 거리가 c임을 의미한다. (1 ≤ a,b ≤ V, 1 ≤ c  ≤ 10,000)

출력

민준이가 찾은 최단 경로 위에 건우가 있다면 "SAVE HIM" 을 아니면 "GOOD BYE" 를 출력한다.

구조화

건우를 거치는지 아닌지 확인

오답 노트

if (cur.l>end) break; 아직 이해못하겠음

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    public static class Node{
        int n;
        int l;
        boolean isP;
        public Node(int n,  int l){
            this.n = n;
            this.l = l;
        }
        public Node(int n,  int l, boolean isP){
            this.n = n;
            this.l = l;
            this.isP = isP;
        }
    }
    public static int v, p, end = 987654321;
    public static boolean ans = false;
    public static int[] dist;
    public static Stack<Integer>[] stacks;
    public static List<Node>[] list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        p = Integer.parseInt(st.nextToken());

        stacks = new Stack[v+1];
        dist = new int[v+1];
        list = new List[v+1];
        for (int i = 1; i <= v; i++) {
            list[i] = new ArrayList<>();
            stacks[i] = new Stack<>();
        }
        // 간선
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            int f = Integer.parseInt(st.nextToken());
            int l = Integer.parseInt(st.nextToken());

            // 양방향
            list[t].add(new Node(f, l));
            list[f].add(new Node(t, l));

        }

        d();
    }

    public static void d(){
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2)->o1.l-o2.l);
        pq.offer(new Node(1, 0));
        Arrays.fill(dist, 987654321);
        dist[1] = 0;

        while (!pq.isEmpty()){
            Node cur = pq.poll();

            if (cur.n==v){
                if (cur.l>end) {
                    break;
                }
                if (cur.isP) {
                    ans = true;
                    break;
                }
                end = cur.l;
            }

            boolean flag = cur.isP;
            if (cur.n==p){
                flag = true;
            }

            for (Node next:list[cur.n]) {
                if (dist[next.n]<next.l+cur.l)
                    continue;
                dist[next.n] = next.l+cur.l;
                pq.offer(new Node(next.n, dist[next.n], flag));
            }
        }

        if (ans){
            System.out.println("SAVE HIM");
        }
        else
            System.out.println("GOOD BYE");
    }
}

git hub 링크