[Java] 백준 17396 : 백도어

[문제]

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

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을 출력한다.

[예제 입력]

 

[풀이 과정]

이 문제는 유섭이의 챔피언이 상대 넥서스에 가기까지 안들키고 최소 시간을 구하면 되는 문제이다. 갈 수 없다면 -1을 출력하면 된다.

 

유섭이의 챔피언이 넥서스에 가기까지는 다익스트라 알고리즘을 이용하여 넥서스까지의 최소 비용을 구하면된다. 하지만 이 문제의 조건중적 챔피언 혹은 적 와드(시야를 밝혀주는 토템), 미니언, 포탑 등 상대의 시야에 걸리는 곳은 지나칠 수 없다고 나와있다. 즉 갈 수 없는 정점이 존재한다는것이다. 따라서 갈 수 있는 정점만을 통해서 넥서스로 가야한다.

 

그러면 유섭이가 들키지 않고 넥서스로 어떻게 갈 수 있을까?

 

1. boolean 배열을 만들어서 해당 인덱스 번호의 정점을 갈 수 있는지 없는지 체크하도록 하였다. boolean[정점번호]가 true라면 해당 정점으로 갈 수 없다는 의미이다.

2. 다익스트라 알고리즘을 돌면서 현재 정점에서 다음 정점으로 가는 노드를 찾을때 갈 수 있는 정점인지를 판단한다. 즉 boolean[다음 정점 번호] 가  true 라면 그 다음 정점은 탐색할 수 없도록 한다. 여기서 주의할 점은 넥서스도 상대의 진영이기에 상대 시야에 보인다고 판단한다. 하지만 넥서스의 경우에만 방문 가능하다고 문제에서 나와있기때문에 넥서스에 해당 하는 정점 번호이면 탐색을 할 수 있도록 구현해야한다.

 

1, 2번의 방식대로 구현하면 문제 조건에 따라 최소 시간을 구할 수 있다. 그런데 이 문제의 정답률은 약 25%이다. 수상하다. 문제의 입력 조건을 잘 보면 정점의 개수는 최대 10만개이고 간선의 개수는 최대 30만개 이다. 그리고 간선의 비용이 최대 10만이다.  여기서 최악일 경우에 최소 시간이 어떻게 나올지 고려해야한다. 

 

우선 상대방에 시야에 모든 정점이 들어오지 않는다면 모든 정점들을 방문할 수 있다.

이러한 상황에서 최악의 상황은 정점 10만개가 존재하는데 시작점에서 도착점까지 간선 10만의 비용으로 10만 -1 번 간선을 타서 도착지점에 가는 것이다.

 

따라서 나올 수 있는 최소 시간은 10만 (간선비용)  * (10만 -1) (간선 개수) = 9999900000이다. lnt형 범위를 넘긴다.  따라서 최소 시간을 갱신하는 배열의 값을 long형으로 선언하고 값을 구해야 할 것이다. 그리고 초기화 해줄때는 반드시9999900000보다 큰값으로 초기화 해주어야한다.

 

아마도 이런 부분을 생각하지 않고 구현했다면 범위 때문에 틀렸을 가능성이 크다. 혹은 넥서스에 왔는데 못 탐색하게 했다거나... 항상 문제 조건을 잘 읽는것이 중요하다.

 

 

[코드]

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

public class Main17396{

    static class Node {
        int idx;
        long cost;

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

    static long MAX_VALUE = 9999900001L;

    public static void main(String[] args) throws IOException {
        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()); // 간선의 개수


        boolean []isShow = new boolean[N]; //해당 정점이 시야에 보이는지 저장하기 위한 배열

        st = new StringTokenizer(br.readLine());

        for(int i = 0 ; i < N ; i++){
            if(Integer.parseInt(st.nextToken())==1){
                isShow[i]=true; // 시야에 보이는 정점이라면 true;
            }
        }

        //인접 리스트
        ArrayList<Node> [] graph = new ArrayList[N];

        for(int i = 0 ; i < N ; i++){
            graph[i] = new ArrayList<Node>();
        }


        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());

            //양방향 관게 설정
            graph[from].add(new Node(to,cost));
            graph[to].add(new Node(from,cost));
        }


        long dist = dijkstra(N,graph,isShow);

        // dist 가 MAX_VALUE 라면 넥서스 까지 가지 못하는 경우이기때문에 -1를 출력하고 그렇지 않으면 최소비용을 출력한다.
        System.out.println(dist==MAX_VALUE?"-1":dist);
    }


    private static long dijkstra (int N ,ArrayList<Node> [] graph , boolean[]isShow) {


        PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> Long.compare(o1.cost,o2.cost));
        //정점까지의 최소비용을 갱신하는 배열을 long으로 잡은 이유는
        //어느 한 정점에서 정점까지 비용이 최대 10만이다.
        // 그런데 최대로 정점이 10만개가 주어질 수 있다.
        //이렇게 되었을때 최악의 경우 10만 * 약 10 만 = 100억 의 비용이 발생하기때문에 long형으로 선언해야한다.
        long [] dist = new long[N];
        for(int i = 0; i < N; i++){
            dist[i] = MAX_VALUE;

        }

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

        while (!queue.isEmpty()){

            Node currNode = queue.poll();



            //도착지점에 오면 break;
            if(currNode.idx==N-1)break;
            if(dist[currNode.idx] < currNode.cost) continue;


            for(int i = 0 ; i< graph[currNode.idx].size();i++){

                Node nxtNode = graph[currNode.idx].get(i);

                //만약 다음 이동할 노드가 적에 시야에 보인다면 탐색하지 않는다. 넥서스의 경우 이동가능
                if(isShow[nxtNode.idx] && nxtNode.idx!=N-1)continue;

                if(dist[nxtNode.idx] > dist[currNode.idx]+ nxtNode.cost ){
                    dist[nxtNode.idx] = dist[currNode.idx]+ nxtNode.cost;
                    queue.offer(new Node(nxtNode.idx,dist[nxtNode.idx]));

                }
            }

        }

        return dist[N-1];
    }

}

 

[결과]

 

* 틀린 설명이 있다면 지적해주세요 : )