백준 No.17396 백도어 - JAVA

문제

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

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

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

 

 

5 7
0 0 0 1 1
0 1 7
0 2 2
1 2 4
1 3 3
1 4 6
2 3 2
3 4 1

 

풀이

처음에 dist배열을 int로 받아서 틀렸다... 한참 찾다가 답을 통해 알았따....

다른 풀이와 같이 다익스트라를 사용하는데 특이점은 먼저 주어진 00011을 걸러야한다.

0은 보이지 않는 곳이고, 1은 시야에 보이는 곳이므로 보이지 않는 곳으로 넥서스까지 가야한다는 소리인 것 같다. 결국 1이면 들어갈 수 없다는 소리로 파악했고 이게 맞는 거 같다.  

for(Node next : list.get(now.node)){
    if(next.node != N-1 && !sight[next.node]) continue;

    if(dist[next.node] > dist[now.node] + next.cost){
        dist[next.node] = dist[now.node] + next.cost;
        queue.add(new Node(next.node,dist[next.node]));
    }
}

그래서 위와 같은 핵심 코드에서 for문을 돌 때 만약 1인 경우 최단경로를 구하지 않도록 했고 넥서스는 예외다.

그리고 sight배열은 애초에 입력이 주어질 때 true/false를 지정하도록 구성했다. 

해당 문제는 푼 시간보다 int를 long으로 바꾸는 시간이 더 오래걸렸다. 정말 화가 난다.

우선순위 큐에서 long 타입을 int 타입으로 오름차순정렬하려면 

아래처럼 사용하면된다.

 

 

PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> Math.toIntExact(o1.cost - o2.cost));

 

 

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

public class Main {


    static int N,M;
    static ArrayList<ArrayList<Node>> list =new ArrayList<>();
    static boolean sight[];
    static long dist[];

    static boolean visited[];



    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 boolean[N];
        dist = new long[N];
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N ; i++) {
            int temp = Integer.parseInt(st.nextToken());
            if(temp == 1 ){
                sight[i] = false;
            }else{
                sight[i] = true;
            }
        }

        for (int i = 0; i < N ; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < M ; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            list.get(a).add(new Node(b,c));
            list.get(b).add(new Node(a,c));

        }

        Arrays.fill(dist,Long.MAX_VALUE);

        visited = new boolean[N];

        dijstra();


        System.out.println(dist[N-1] != Long.MAX_VALUE ? dist[N-1] : -1);

    }

    static void dijstra(){
        PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> Math.toIntExact(o1.cost - o2.cost));
        dist[0] = 0;
        queue.add(new Node(0,0));

        while (!queue.isEmpty()){
            Node now = queue.poll();

            if(visited[now.node]) continue;

            visited[now.node] = true;

            for(Node next : list.get(now.node)){
                if(next.node != N-1 && !sight[next.node]) continue;

                if(dist[next.node] > dist[now.node] + next.cost){
                    dist[next.node] = dist[now.node] + next.cost;
                    queue.add(new Node(next.node,dist[next.node]));
                }
            }
        }
    }

    static class Node{
        int node;
        long cost;

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

    }
}