[백준 9370 : JAVA] 미확인 도착지 / 다익스트라

문제

---

 

 

 

풀이

---

최단 경로를 구하는 문제로 다익스트라 알고리즘을 이용해 풀 수 있는 문제다.

위의 예제 입력에서 첫 번째 테스트 케이스를 그래프로 시각화해보자.

 

특정 목적지로의 최단 경로 중특정 경로를 포함하는지를 확인하는게 문제의 포인트다.

위 케이스의 최단 경로에서 2에서 3으로 가는 경로가 포함되어 있는지 확인하기 위해 생각해볼 수 있는 방법은 두 가지다.

첫 번째,

(1 -> 2 최단거리) + (2 -> 3 최단거리) + (3 -> 5 최단거리) == (1 -> 5 최단거리) 또는
(1 -> 3 최단거리) + (3 -> 2 최단거리) + (2 -> 5 최단거리) == (1 -> 5 최단거리)

 

위 방법은 가장 간단하게 생각해볼 수 있는 방법이지만, 다익스트라 함수를 여러 번 호출해야하기 때문에 비효율적인 방법이다.

 

 

두 번째,

간선의 가중치를 저장할 때 2를 곱한 값을 저장해 짝수로 만들고, 확인하고자 하는 간선의 가중치에는 -1를 해줘 홀수로 만든다.

 

위와 같이 저장한 후 최단 거리를 확인했을 때 홀수가 나온다면 해당 경로를 포함하는 것이고, 짝수라면 포함하지 않는다라는걸 알 수 있다.

 

 

 

코드

---

Java 언어를 이용해 코드로 살펴보자.

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

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static final int INF = 100_000_000;
    private static int T;
    private static int V, E, t;
    private static List<List<Node>> list;
    private static int dist[];
    private static List<Integer> candidate;

    static class Node implements Comparable<Node> {

        int v, weight;

        public Node(int v, int weight) {
            this.v = v;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            return weight - o.weight;
        }
    }

    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());
            t = Integer.parseInt(st.nextToken());

            dist = new int[V + 1];
            Arrays.fill(dist, INF);

            list = new ArrayList<>();
            for (int j = 0; j < V + 1; j++)
                list.add(new ArrayList<>());

            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());

            for (int j = 0; j < E; j++) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                int weight = Integer.parseInt(st.nextToken());

                if ((u == g && v == h) || (u == h && v == g)) {
                    list.get(u).add(new Node(v, weight * 2 - 1));
                    list.get(v).add(new Node(u, weight * 2 - 1));
                } else {
                    list.get(u).add(new Node(v, weight * 2));
                    list.get(v).add(new Node(u, weight * 2));
                }
            }

            // 목적지 후보를 저장한다.
            candidate = new ArrayList<>();
            for (int j = 0; j < t; j++)
                candidate.add(Integer.parseInt(br.readLine()));

            dijkstra(start);

            Collections.sort(candidate);

            for (int num : candidate) {
                if (dist[num] % 2 == 1) bw.write(num + " ");
            }
            bw.write("\n");
        }

        br.close();
        bw.close();
    }

    private static void dijkstra(int u) {
        boolean[] visited = new boolean[V + 1];
        PriorityQueue<Node> pq = new PriorityQueue<>();

        dist[u] = 0;
        pq.add(new Node(u, 0));

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

            if (visited[currentNode.v]) continue;
            visited[currentNode.v] = true;

            for (Node node : list.get(currentNode.v)) {
                if (!visited[node.v] && dist[node.v] > dist[currentNode.v] + node.weight) {
                    dist[node.v] = dist[currentNode.v] + node.weight;
                    pq.add(new Node(node.v, dist[node.v]));
                }
            }
        }
    }
}

 

 

 

참고자료

---

[1] https://dragon-h.tistory.com/22