[백준] BOJ 17396 백도어 (골드 5)

문제

---

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

17396: 백도어

---

해설

---

1. 0 -> N - 1로 가는 최단 경로를 구하는 것 (그래프에서 양의 가중치이므로 다익스트라를 수행)
   
   
2. 이떄, from, to 정점 둘 중 하나라도 와드가 있는 경우 (보이는 경우)는 간선 자체를 추가하지 않는다.
   (어차피 해당 정점으로 가면 안되기 때문에)
   
   
3. 하지만, 넥서스의 경우 무조건 보이며 도착점으로 설정되어야 한다.
   (따라서, 넥서스인 경우 넥서스에서 출발하는 간선은 추가하지 않고 넥서스를 도착으로 하는 간선만을 추가한다.)
   
   
4. 이를 통해 기본적인 다익스트라를 수행한다.
   
   
5. 이때, 주의해야할 점은 해당 코드에서 이 부분이 빠지면 시간 초과가 발생한다.
   

   if(node.cost > dist[node.vertex]) continue;

   
   
   • 이유는 우선순위가 낮아 나오지 못한 노드가 우선순위가 높은 노드들에 의해 갱신된 상태인데도 for문을 통해 모두 확인하기 때문
   • 즉, 어차피 해당 노드 이전에 PQ에서 나온 값들에 의해 갱신되어 더 최소인 상태인데
   • 이제야 나온 값으로 갱신해봤자 최소로 갱신도 못시키고 for문 돌며 시간만 늘어난다.
6. 또한, 100,000 * 100,000이 결과의 최대 값이므로 long으로 선언해주며, + 1한 값을 INF로 설정해준다.
   
   
7. 다익스트라를 수행하며, 현재 꺼낸 노드의 정점이 N-1이면 이때의 dist[N-1]을 반환하여 출력한다.
   
   
8. 만약 모든 노드를 다 순회하여 최단으로 갱신하여도 N-1정점에 도달하지 못하면 -1을 반환하고 출력한다.

---

코드 (다익스트라)

---

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

public class BOJ17396 {
    static Node[] adjList;
    static boolean[] ward;
    static int N, M;
    static final long INF = 100_000L * 100_000L + 1;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        ward = new boolean[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            ward[i] = Integer.parseInt(st.nextToken()) == 0;
        }

        adjList = new Node[N];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            //두 정점이 모두 보이지 않을때만 가도록 인접 리스트 생성
            //넥서스는 무조건 보이므로 제외
            if ((ward[from] && ward[to])) {
                adjList[from] = new Node(to, cost, adjList[from]);
                adjList[to] = new Node(from, cost, adjList[to]);
            } else if (from == N - 1 && ward[to]) {
                adjList[to] = new Node(from, cost, adjList[to]);
            } else if (to == N - 1 && ward[from]) {
                adjList[from] = new Node(to, cost, adjList[from]);
            }
        }

        System.out.println(dijkstra());
    }

    private static long dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(0, 0, null));
        long[] dist = new long[N];
        Arrays.fill(dist, INF);
        dist[0] = 0;

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

            //중요!!! 시간 초과 포인트
            //이전에 들어왔지만 우선순위가 늦어서 즉, 코스트가 높아서 못나오다가 뒤늦게 나온 node
            //해당 node는 이미 우선순위가 높은 노드들에 의해 dist[node.vertex]가 갱신된 상태인데
            //우선순위가 낮아서 이제야 나왔음 -> 이것도 다시 for문을 돌면 어차피 갱신안됨
            //이미 다른 노드들에 의해 더 작은 값으로 갱신이 되었으니까!!
            //따라서 해당 노드는 폐기해야함 (for문을 굳이 더 안돌아도 되니 시간도 효율적)
            if(node.cost > dist[node.vertex]) continue;
            if (node.vertex == N - 1) return dist[N - 1];

            for (Node n = adjList[node.vertex]; n != null; n = n.next) {
                if (dist[n.vertex] > dist[node.vertex] + n.cost) {
                    dist[n.vertex] = dist[node.vertex] + n.cost;
                    pq.offer(new Node(n.vertex, dist[n.vertex], null));
                }
            }
        }

        return -1;
    }
}

class Node implements Comparable<Node> {
    int vertex;
    long cost;
    Node next;

    public Node(int vertex, long cost, Node next) {
        this.vertex = vertex;
        this.cost = cost;
        this.next = next;
    }

    @Override
    public int compareTo(Node o) {
        return Long.compare(this.cost, o.cost);
    }
}

---

결론

---

다익스트라의 기본 정의에 대해 다시 생각해볼 수 있었다!.

---