17396 - 백도어[G5]

 

문제

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

유섭이는 무척이나 게으르다. 오늘도 할 일을 모두 미뤄둔 채 열심히 롤을 하던 유섭이는 오늘까지 문제를 내야 한다는 사실을 깨달았다. 그러나 게임은 시작되었고 지는 걸 무척이나 싫어하는 유섭이는 어쩔 수 없이 백도어를 해 게임을 최대한 빠르게 끝내기로 결심하였다.

최대한 빨리 게임을 끝내고 문제를 출제해야 하기 때문에 유섭이는 최대한 빨리 넥서스가 있는 곳으로 달려가려고 한다. 유섭이의 챔피언은 총 N개의 분기점에 위치할 수 있다. 0번째 분기점은 현재 유섭이의 챔피언이 있는 곳을, N-1 번째 분기점은 상대편 넥서스를 의미하며 나머지 1, 2, ..., N-2번째 분기점은 중간 거점들이다. 그러나 유섭이의 챔피언이 모든 분기점을 지나칠 수 있는 것은 아니다. 백도어의 핵심은 안 들키고 살금살금 가는 것이기 때문에 적 챔피언 혹은 적 와드(시야를 밝혀주는 토템), 미니언, 포탑 등 상대의 시야에 걸리는 곳은 지나칠 수 없다.

입력으로 각 분기점을 지나칠 수 있는지에 대한 여부와 각 분기점에서 다른 분기점으로 가는데 걸리는 시간이 주어졌을 때, 유섭이가 현재 위치에서 넥서스까지 갈 수 있는 최소 시간을 구하여라.

입력

첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000)

두 번째 줄에 각 분기점이 적의 시야에 보이는지를 의미하는 N개의 정수 a0, a1, ..., aN-1가 공백으로 구분되어 주어진다. ai가 0이면 i 번째 분기점이 상대의 시야에 보이지 않는다는 뜻이며, 1이면 보인다는 뜻이다. 추가적으로 a0 = 0, aN-1 = 1이다., N-1번째 분기점은 상대 넥서스이기 때문에 어쩔 수 없이 상대의 시야에 보이게 되며, 또 유일하게 상대 시야에 보이면서 갈 수 있는 곳이다.

다음 M개의 줄에 걸쳐 세 정수 a, b, t가 공백으로 구분되어 주어진다. (0 ≤ a, b < N, a ≠ b, 1 ≤ t ≤ 100,000) 이는 a번째 분기점과 b번째 분기점 사이를 지나는데 t만큼의 시간이 걸리는 것을 의미한다. 연결은 양방향이며, 한 분기점에서 다른 분기점으로 가는 간선은 최대 1개 존재한다.

 

 

풀이

핵심 풀이는 '1' 이 속한 노드를 배제해 버리는 것이다.

기존 풀이에 시간 초과 문제가 발생한 부분인데, 이를 visit 배열을 통해 중복된 노드 (이미 방문했던 노드)를 배제시키면서 다익스트라 문제를 통해 풀이를 해결하였다.

 

코드

 

import java.io.*;
import java.util.*;
class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        List<Node> graph = new ArrayList<>(); //그래프

        // 그래프 초기화
        for (int i = 0; i < n; i++) {
            graph.add(new Node(i));
        }

        // 각 분기점이 적의 시야에 보이는지 여부 체크
        st = new StringTokenizer(br.readLine());
        boolean[] visible = new boolean[n];
        for (int i = 0; i < n; i++) {
            int visibility = Integer.parseInt(st.nextToken());
            visible[i] = (visibility == 1);  // 적의 시야에 보이는지 여부 저장
        }

        graph.get(0).dist = 0; //최초 이동 거리는 0임

        //M개의 분기점
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            // 적의 시야에 보이는 분기점들로 가는 경로 간선 예외 처리
            if ((visible[start] && start != n - 1) || (visible[end] && end != n - 1)) {
                continue; // 시야에 걸리는 노드로의 간선을 제외
            }

            graph.get(start).edges.add(new Edge(end, weight));
            graph.get(end).edges.add(new Edge(start, weight));

        }

        //PQ 생성
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(graph.get(0)); //최초 노드 삽입
        boolean[] visit = new boolean[n];
        
        while (!pq.isEmpty()) {
            Node now = pq.poll(); //현재 노드
            if (visit[now.idx]) continue;
            visit[now.idx] = true;
                
            if (now.dist > graph.get(now.idx).dist) continue; //큐에 있을 동안 지금 꺼낸 노드보다 낮은 값으로 갱신되었을 수도 있음

            for (int i = 0; i < now.edges.size(); i++) {
                Edge edge = now.edges.get(i); //간선
                Node nextNode = graph.get(edge.dest);

                //nextNode로 가는 dist는 현재 Node의 dist + edge의 weight이다
                long newDist = now.dist + edge.weight;
                if(nextNode.dist > newDist) {
                    nextNode.dist = newDist;
                    pq.add(nextNode);
                }
            }
        }

        long res = graph.get(n - 1).dist;
        if (res == Long.MAX_VALUE) System.out.println(-1);
        else System.out.println(res);
    }


}
class Node implements Comparable<Node> {
    long dist = Long.MAX_VALUE;
    int idx;
    List<Edge> edges = new ArrayList<>();
//    boolean canGo = false;
    public Node(int idx) {
        this.idx = idx;
    }

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

class Edge {
    int dest; //도착지 idx
    int weight;

    public Edge(int dest, int weight) {
        this.dest = dest;
        this.weight = weight;
    }
}