백준 17396번 - 백도어 시간초과 문제 해결하기(Java)

 

코드 :

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.util.Comparator.*;

public class Main {

    static class Point {
        int no;
        long time;

        public Point(int no, long time) {
            this.no = no;
            this.time = time;
        }

        public long getTime() {
            return time;
        }
    }

    private static List<Point>[] adjList;

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

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

        boolean[] cannotGo = new boolean[N];
        long[] d = new long[N];
        Arrays.fill(d, Long.MAX_VALUE);

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int visible = Integer.parseInt(st.nextToken());

            if (visible == 1) {
                cannotGo[i] = true;
            }
        }

        // 마지막 분기점은 시야에 보이지만 가야하는 곳이다.
        cannotGo[N - 1] = false;

        if (cannotGo[0]) {
            System.out.print("-1");
            System.exit(0);
        }

        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 t  = Integer.parseInt(st.nextToken());

            adjList[a].add(new Point(b, t));
            adjList[b].add(new Point(a, t));
        }

        PriorityQueue<Point> pq = new PriorityQueue<>(comparingLong(Point::getTime));
        pq.offer(new Point(0, 0));
        d[0] = 0;

        while (!pq.isEmpty()) {
            Point now = pq.poll();
            cannotGo[now.no] = true; // 방문체크

            if (now.time > d[now.no]) continue;
            if (now.time > d[N - 1]) break;

            for (Point next : adjList[now.no]) {
                if (!cannotGo[next.no] && d[next.no] > now.time + next.time) {
                    d[next.no] = now.time + next.time;
                    pq.offer(new Point(next.no, d[next.no]));
                }
            }
        }

        if (d[N-1] == Long.MAX_VALUE) {
            System.out.print("-1");
        } else {
            System.out.print(d[N-1]);
        }
    }
}
// 한 분기점에서 다른 분기점으로 가는 간선은 최대 1개 존재한다.

다익스트라를 반복적으로 풀어서 외우며 익히던 도중, 기본적인 다익스트라 문제인 줄 알았는데 시간초과가 계속나서 풀지를 못했습니다. 검색해도 자바 풀이는 많이 안나와서.. 난감해하던 차에 운좋게 해결책을 발견해서 공유하게 되었습니다.

 

링크의 내용을 참고해서 제가 이해한 내용을 바탕으로 작성했습니다. 틀린 부분 있으면 지적해주시면 감사하겠습니다.

풀이 :

기존에 77행의 `if (now.time > d[now.no]) continue;` 해당 부분 없이 구현했는데 계속해서 시간초과가 났다. 운좋게 아래 참고링크와 같은 자료가 백준에 있는걸 알게 되었고, 바탕으로 수정해서 통과했다. (여태 이런 글이 있는지도 몰랐습니다.) 7번에서 해결책을 얻을 수 있었다. "필독"이라는 키워드로 검색하면 많이 나온다!

 

 

 

77행의 코드를 빼게 되면,

• for문 안에서 인접 노드들을 탐색하면서 특정 최소 거리가 더 작은 값으로 여러 번 갱신될 수 있다.
• 예시로 최소 거리를 뜻하는 d배열에서 d[10]의 값(임의로 지정한 것이지 10에는 아무 의미가 없습니다.)을 10,000으로 가정하자. 다른 지름길(최소 경로)을 발견하면서 9999, 9998, 9800 과 같이 무수히 갱신될 수 있다.
• d[10]의 값은 결국에는 가장 작은 값으로 갱신된다. 만약 d[10]의 갱신된 결과가 1,000이라고 가정하면 특정 시점에 1,001 ~ 9999에 해당하는 정점들의 우선순위큐에 들어가 있는 상태가 된다.
• 우선순위 큐이기때문에 거리가 1,000인 정점이 가장 먼저 poll 될 것이다. 하지만 (1 차이로 계속 갱신됐다고 가정하면) 나머지 9000개 가량의 정점이 큐 안에 존재할 수 있다.
• 탐색이 끝나지 않아 운이 없으면 9000개 가량의 정점이 poll될 것이다. for문 내부에 if문으로 방문여부를 체크하기 때문에 인접 정점을 탐색하지 않지만, 결국 9,000번 가량 순회하게 된다.
• 여기서 정점은 최대 10만개, 간선은 30만개이다. 10만번 씩 순회를 하지 않을까 싶다. 정확한 회수는 모르겠다.

 

체크해야할 것들...

• 우선순위 큐에서 나올때 이미 갱신된 거리에 대해 체크를 해주는가?
• INF 값의 설정이 적절한가? -> 자바의 경우 Integer 범위를 넘지 않는지 확인해야 한다. -> (간선 가중치의 최댓값) * (정점 최대 개수 - 1)을 계산해보자.
• 우선순위 큐에서 나올때 방문 여부를 체크해야 다익스트라가 전체 동작한다.
• 정점 간에 여러 개의 간선이 존재한다면, 더 작은 값으로 초기화해야 한다.
• 제자리로 이동하는 간선이 있는지 체크 -> 이걸 체크해야 통과하는 문제도 있던데 방문체크로 해결이 안되는건지 이해가 아직 안갔다.

더 추가적인 내용은 아래 링크에 있습니다.

참고 :

https://www.acmicpc.net/board/view/34516

글 읽기 - ★☆★☆★ [필독] 최단경로 (다익스트라 알고리즘) FAQ ★☆★☆★