BOJ G2 9370 미확인도착지 JAVA

9370번: 미확인 도착지

---

문제 읽기

일단 처음에 읽었을 때는 다익스트라로 풀면 되겠다 생각이 들었고, 그 사이에 g와 h 사이의 도로를 지나갔다면 별도의 배열로 표시해주자고 생각했다.

하지만! 예제는 나왔지만 제출했더니 틀렸다(근데 예제가 너무 유하게 줘서 웬만하면 예제는 다 맞고 내면 틀리는 거 같다. 그래서 정답 비율이 25%..)

 

그래서 질문 게시판 뒤져보니 이런 말들이 있었다.

글 읽기 - 반례를..모르겠습니다

!!!!!

최단 경로가 여러 개 나오는 경우를 딱히 생각해주지 않았다.

그래서 위와 같은 풀이법으로 다시 풀어보았다.

---

문제 풀기

다익스트라만 할 줄 안다면 간단하다.

 

문제에서 구하는 바를 요약하면, “시작 지점과 목표 지점이 있고, 그 목표 지점까지 최단경로로 갈 때 특정 하나의 도로를 지나가는가?” 이다.

 

따라서 최단 경로로 갔을 때와, 특정 도로를 필수적으로 지나갔을 때의 비용이 같다면, 정답이 되는 것이다.

즉, 시작점이 s이고 중간에 지나는 도로가 노드 g와 h 사이의 도로라고 한다면 목적 노드 target까지 가기까지 다음과 같은 경우의 수가 나온다.

 

1. s → target ⇒ 다익스트라
2. s → g → h → target
   1. s → g
   2. g → h
   3. h → target ⇒ 다익스트라
3. s → h → g → target
   1. s → h
   2. h → g
   3. g → target ⇒ 다익스트라

따라서 s, h, g를 시작점으로 하여 총 세 번의 다익스트라를 수행한다면, 답을 구할 수 있다.

---

코드

package ps.GraphSearch;

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

public class BOJ_G2_9370_미확인도착지 {
    /*
    1. 출발지에서 모든 지점까지 다익스트라
        + 경로를 저장하거나 dist 배열과 크기가 같은 배열을 만들어서 g와 h 사이의 도로를 거치는 지 확인하며..
    2. g랑 h 사이를 거치는 후보 지점들에 대해 오룸차순으로 출력
     */
    static class Node{
        int no;
        int cost;
        public Node(int no, int cost){
            this.no = no;
            this.cost = cost;
        }
    }

    static int N, M, targetT;
    static int start, g, h;
    static List<List<Node>> graph;
    static int[] targetNodes;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine());
        StringBuilder sb = new StringBuilder();
        while(T-- > 0){
            StringTokenizer st = new StringTokenizer(in.readLine());
            N = Integer.parseInt(st.nextToken()); //교차로(노드) 개수
            M = Integer.parseInt(st.nextToken()); //도로 개수
            targetT = Integer.parseInt(st.nextToken()); //목적지 후보 개수

            st = new StringTokenizer(in.readLine());
            start = Integer.parseInt(st.nextToken()); //시작 위치
            g = Integer.parseInt(st.nextToken()); //중간 지점1
            h = Integer.parseInt(st.nextToken()); //중간 지점2

            //노드들의 정보를 입력받자
            graph = new ArrayList<>(); //1~N
            for (int i = 0; i < N+1; i++){
                graph.add(new ArrayList<>());
            }

            int midL = 0;
            for (int i = 0; i < M; i++){
                st = new StringTokenizer(in.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int d = Integer.parseInt(st.nextToken());
                graph.get(a).add(new Node(b, d));
                graph.get(b).add(new Node(a, d));
                if ((a == g && b == h) || (a == h && b == g)) midL = d;
            }

            //목적지 후보들을 입력받자
            targetNodes = new int[targetT];
            for (int i = 0; i < targetT; i++){
                targetNodes[i] = Integer.parseInt(in.readLine());
            }

            //logic
            /*
            1. S -> 목적지 후보들 -- 다익스트라
            2. S -> G -> H -> 목적지후보들
                2.1 S -> G
                2.2 G -> H
                2.3 H -> 목적지후보들 -- 다익스트라
            3. S -> H -> G -> 목적지후보들
                2.1 S -> H
                2.2 H -> G
                2.3 G -> 목적지 후보들 -- 다익스트라

            =>다익스트라 세 번 수행
             */

            int[] distFromStoAll = new int[N+1]; //1~N
            int[] distFromHtoAll = new int[N+1]; //1~N
            int[] distFromGtoAll = new int[N+1]; //1~N
            dijkstra(distFromStoAll, start);
            dijkstra(distFromHtoAll, h);
            dijkstra(distFromGtoAll, g);

            Arrays.sort(targetNodes);
            for (int target : targetNodes){
                if (distFromStoAll[target] == (distFromStoAll[g] + midL + distFromHtoAll[target])
                || distFromStoAll[target] == (distFromStoAll[h] + midL + distFromGtoAll[target])) sb.append(target).append(" ");
            }
            sb.append("\\n");
        }
        System.out.println(sb);
    }
    static int INF = 1000*20000;

    private static void dijkstra(int[] dist, int start) {
        //pq, dist, (?)
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.cost - o2.cost;
            }
        });
        Arrays.fill(dist, INF);
        pq.offer(new Node(start, 0));
        dist[start] = 0;

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

            for (Node adj : graph.get(cur.no)){
                if (dist[adj.no] > dist[cur.no] + adj.cost){
                    dist[adj.no] = dist[cur.no] + adj.cost;
                    pq.offer(new Node(adj.no, dist[adj.no]));
                }
            }
        }
    }
}