백준 17396 (백도어) - java

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

17396번: 백도어

문제 :

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

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

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

 

유형 : 다익스트라

 

접근

• 입력의 크기가 굉장히 크기 때문에 다익스트라 최적화를 해야 한다.
  • 방문 배열 추가 -> 가지가 뻗어 나간 적 있는 정점이라면 continue
  • 우선순위 큐 사용 -> 이중 반복문과 비교하여 시간 복잡도에서 우위 
• 넥서스의 시야 정보가 1인데 이를 0으로 바꾸는 것을 추천한다. -> if 구절이 복잡해진다.
• 입력받는 간선 정보에 대햐여 시야가 밝혀진 정점을 포함한다면 그래프에 간선으로 추가하지 않는다.
  • 이 작업을 위해 시야 정보를 1에서 0으로 바꿔준다.

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;

    static int[] sight;
    static ArrayList<Node>[] graph;
    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());

        sight = new int[n];
        graph = new ArrayList[n];

        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0;i<n;i++){
            sight[i] = Integer.parseInt(st.nextToken());
            graph[i] = new ArrayList<>();
        }
        sight[n-1] = 0;

        for(int i=1;i<=m;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            long v = Integer.parseInt(st.nextToken());

            if(sight[x] == 1 || sight[y] == 1){
                continue;
            }

            graph[x].add(new Node(y,v));
            graph[y].add(new Node(x,v));
        }

        bs();
        br.close();
    }

    static void bs(){
        boolean[] visit = new boolean[n];
        long[] dis = new long[n];
        for(int i=1;i<n;i++){
            dis[i] = Long.MAX_VALUE;
        }
        dis[0] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> Long.compare(x.c,y.c)
        );
        pq.add(new Node(0,0));

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

            if(visit[cur.v])
                continue;

            visit[cur.v] = true;

            for(Node next : graph[cur.v]){
                if(sight[next.v] == 1)
                    continue;

                if(dis[next.v] > dis[cur.v] + next.c){
                    dis[next.v] = dis[cur.v] + next.c;
                    pq.add(new Node(next.v,dis[next.v]));
                }
            }
        }

        if(dis[n-1] != Long.MAX_VALUE){
            System.out.println(dis[n-1]);
        }

        else{
            System.out.println(-1);
        }
    }
}
class Node{
    int v;
    long c;

    Node(int v,long c){
        this.v = v;
        this.c = c;
    }
}