[BJ]9370. 미확인도착지

BJ G2 9370 미확인 도착지

 

 

문제링크

9370번: 미확인 도착지 (acmicpc.net)

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/wjTd35oX_ig

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BJ_G2_9370_미확인도착지 {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    static StringTokenizer tokens;

    static int T;
    static int V, E, TC;
    static int S, G, H;
    static LinkNode[] graph;
    static int[] targets;

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
        T = Integer.parseInt(input.readLine());
        for (int t = 0; t < T; t++) {
            tokens = new StringTokenizer(input.readLine());
            V = Integer.parseInt(tokens.nextToken()) + 1; // 정점의 개수
            E = Integer.parseInt(tokens.nextToken()); // 간선의 개수
            TC = Integer.parseInt(tokens.nextToken()); // 목적지의 개수

            tokens = new StringTokenizer(input.readLine());
            S = Integer.parseInt(tokens.nextToken()); // 시작점
            G = Integer.parseInt(tokens.nextToken()); // 필수경로 정점 1
            H = Integer.parseInt(tokens.nextToken()); // 필수경로 정점 2

            graph = new LinkNode[V];
            for (int e = 0; e < E; e++) {
                tokens = new StringTokenizer(input.readLine());
                int a = Integer.parseInt(tokens.nextToken()); // 간선 시점
                int b = Integer.parseInt(tokens.nextToken()); // 간선 종점
                int c = Integer.parseInt(tokens.nextToken()) * 2; // 간선 비용
                if ((a == G && b == H) || (a == H && b == G)) {
                    c--;
                }
                // 양방향 그래프
                graph[a] = new LinkNode(b, c, graph[a]);
                graph[b] = new LinkNode(a, c, graph[b]);

            }

            targets = new int[TC];
            for (int tc = 0; tc < TC; tc++) {
                targets[tc] = Integer.parseInt(input.readLine());
            }

            // 정답 출력 시 target은 낮은 것 부터
            Arrays.sort(targets);
            // 최단 경로 찾기
            dijkstra();
        }
        System.out.println(output);
    }

    private static void dijkstra() {
        // 필요한 장치들
        int[] accumCost = new int[V];
        boolean[] visited = new boolean[V];
        PriorityQueue<LinkNode> pq = new PriorityQueue<>();

        // 초기 설정
        Arrays.fill(accumCost, Integer.MAX_VALUE);
        pq.offer(new LinkNode(S, 0));
        accumCost[S] = 0;

        while (!pq.isEmpty()) {
            LinkNode head = pq.poll();

            if (visited[head.i]) {
                continue;
            }

            visited[head.i] = true;

            LinkNode next = graph[head.i];
            while (next != null) {
                if (!visited[next.i] && accumCost[next.i] > accumCost[head.i] + next.c) {
                    accumCost[next.i] = head.ac + next.c;
                    pq.offer(new LinkNode(next.i, accumCost[next.i]));
                }
                next = next.pre;
            }
        }
        // dijkstra 종료
        // 연결된 지점 중에서 목적지의 후보지는?
        for (Integer t : targets) {
            if (accumCost[t] != Integer.MAX_VALUE && accumCost[t] % 2 == 1) {
                output.append(t).append(" ");
            }
        }
        output.append("\n");
    }

    static class LinkNode implements Comparable<LinkNode> {
        int i; // 정점 번호
        int c; // 비용
        int ac; // 시작점에서 해당 정점까지의 누적 비용
        LinkNode pre; // 이전 노드

        public LinkNode(int i, int ac) {
            this.i = i;
            this.ac = ac;
        }

        // 그래프를 생성하기 위한 생성자.
        public LinkNode(int i, int c, LinkNode pre) {
            this.i = i;
            this.c = c;
            this.pre = pre;
        }

        public int compareTo(LinkNode o) {
            return Integer.compare(this.ac, o.ac);
        }

    }

    // REMOVE_START
    private static String src = "1\r\n" +
            "4 4 1\r\n" +
            "1 2 4\r\n" +
            "1 2 3\r\n" +
            "2 4 4\r\n" +
            "1 3 4\r\n" +
            "3 4 3\r\n" +
            "4";
    // REMOVE_END
}