백준 10282 자바 - 해킹 (BOJ 10282 JAVA)

문제 : https://www.acmicpc.net/problem/10282

 

 

  가중치가 있는 방향 그래프에서 한점에서 시작해, 다른 모든 정점으로의 최단거리를 찾는 문제이다. 출력해야 하는 '총 감염되는 컴퓨터 수'는 최단거리가 무한대가 아닌 경우 즉 도달할 수 있다면 감염되는 컴퓨터이다. '마지막 컴퓨터가 감염되기까지 걸리는 시간'은 모든 정점으로의 최단거리 중 최대치를 출력하면 된다.

 

  가중치가 있으므로 일단 BFS는 사용할 수 없고, DFS로는 시간초과를 피할 수 없다. Floyd-Warshall로는 O(100*10000^3) 이므로 역시 시간내에 통과할 수 없다. 쉽게 생각할 수 있는 이 문제에 딱 맞는 알고리즘은 다익스트라(dijkstra)이다. 시간복잡도는 대략 O(ElogV) 정도로 잡는다. -> 테스트케이스까지해서 대략 O(100000*4*100) 정도 -> 시간제한이 2초이므로 충분히 가능할 것임을 예상할 수 있다.

 

  다익스트라에 대해서는 나중에 '알고리즘' 카테고리에 따로 적을 예정이다. 이하 코드는 힙을 이용한 다익스트라를 적용한 코드이다. 사실 엄청 유명한 알고리즘이라서(흔히 네비게이션에서 쓰는 알고리즘으로 유명함) 코드는 구현자체 보다는 코드를 최대한 깔끔하게 짜보는데 집중했다.

 

 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/10200/BOJ_10282.java

import java.io.DataInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

class Pos {
    int to, dist;
    public Pos(int to, int dist) {
        this.to = to;
        this.dist = dist;
    }
}

public class Main {
    private int[] dijkstra(int n, int c, ArrayList<Pos>[] edge) {
        int[] res = new int[n+1];
        Arrays.fill(res, Integer.MAX_VALUE);

        PriorityQueue<Integer> pq = new PriorityQueue();
        pq.add(c);
        res[c] = 0;

        while (!pq.isEmpty()) {
            int cur = pq.poll();
            for (Pos pos : edge[cur]) {
                int next = pos.to;
                if (res[next] > res[cur]+pos.dist) {
                    res[next] = res[cur]+pos.dist;
                    pq.add(next);
                }
            }
        }
        return res;
    }

    private void solution() throws Exception {
        int tc = nextInt();
        StringBuilder answer = new StringBuilder();
        while (tc-->0) {
            int n = nextInt();
            int d = nextInt();
            int c = nextInt();

            ArrayList<Pos>[] edge = new ArrayList[n+1];
            for (int i = 1; i <= n; i++) {
                edge[i] = new ArrayList<>();
            }

            while (d-->0) {
                int a = nextInt();
                int b = nextInt();
                int s = nextInt();
                edge[b].add(new Pos(a, s));
            }

            int[] res = dijkstra(n, c, edge);

            int cnt = 0;
            int max = 0;
            for (int i = 1; i <= n; i++) {
                if (res[i] == Integer.MAX_VALUE) continue;
                cnt++;
                if (max < res[i])
                    max = res[i];
            }
            answer.append(cnt).append(' ').append(max).append('\n');
        }
        System.out.print(answer);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }

    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    private static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    private static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}