[알고리즘 / 백준] 10282 - 해킹

www.acmicpc.net/problem/10282

10282번: 해킹

 

문제는 위와 같으며, 이 문제는 다익스트라 알고리즘을 사용하여 문제를 해결할 수 있습니다.

 

1. 주어진 컴퓨터의 관계를 이차원 배열에 기준 컴퓨터(b) 인덱스에 [감염되는 시간(s), 연결된 컴퓨터(a)] 형태로 데이터를 저장합니다.

2. 다익스트라 알고리즘을 수행하여 감염 시작 컴퓨터(c) 부터 연결된 컴퓨터 각각이 감염되는데 걸리는 최소 시간이 담긴 배열을 구합니다.

3. 해당 배열에서 값이 INF (무한대) 가 아닌 값의 수를 세고(count), 그 값들 중 가장 큰 값(가장 오래 걸리는 시간)을 구합니다.

4. 위에서 구한 count 와 가장 오래 걸리는 시간을 차례대로 출력합니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin
import heapq


def dijkstra(comp, start):
    time = [float('inf')] * len(comp)  # inf (무한대 값으로 초기화)
    time[start] = 0  # 시작 지점은 0으로 초기화

    queue = []
    heapq.heappush(queue, [0, start])  # 우선 순위 큐에 [최단 시간, 노드] 추가

    while queue:
        current_time, current_node = heapq.heappop(queue)  # 가장 빠른 시간 pop

        if current_time > time[current_node]:  # 이미 time 에 최단 시간이 저장된 경우 패스
            continue

        for adj, t in comp[current_node]:  # 연결된 노드 확인
            dist = current_time + t
            if dist < time[adj]:  # "지금까지 현재 노드로 오는데 걸린 최단 시간 + 연결된 노드로 가는 최단 시간" 이 "연결된 노드의 최단 시간" 보다 작은 경우
                time[adj] = dist  # 업데이트 
                heapq.heappush(queue, [dist, adj])  # 업데이트가 된 노드는 다시 우선 순위 큐에 저장

    return time


test_case = int(stdin.readline())
for _ in range(test_case):
    n, d, c = map(int, stdin.readline().split())
    computers = [[] for _ in range(n + 1)]
    for _ in range(d):
        a, b, s = map(int, stdin.readline().split())
        computers[b].append([a, s])
    
    result = dijkstra(computers, c)
    count = 0
    max_time = -1
    for r in result:
        if r != float('inf'):  # 최단 시간이 변경된 경우 (연결된 노드인 경우)
            count += 1
            if max_time < r:
                max_time = r

    print(count, max_time)

 

자바 코드는 다음과 같습니다. (파이썬 코드랑 로직은 같은데 시간 초과가 나네용...ㅠㅠ 해결되면 다시 수정하겠습니다!)

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int test = Integer.parseInt(br.readLine());
        for (int i = 0; i < test; i++) {
            int[] ndc = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            List<ArrayList<int[]>> computers = new ArrayList<>();
            for (int n = 0; n < ndc[0] + 1; n++) {
                computers.add(new ArrayList<>());
            }

            for (int j = 0; j < ndc[1]; j++) {
                int[] abs = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
                computers.get(abs[1]).add(new int[]{abs[0], abs[2]});
            }

            int[] result = dijkstra(computers, ndc[2]);
            int count = 0;
            int max_time = -1;
            for (int r : result) {
                if (r != 100000001) {
                    count += 1;
                    if (max_time < r) {
                        max_time = r;
                    }
                }
            }

            System.out.println(count + " " + max_time);
        }
    }

    private static int[] dijkstra(List<ArrayList<int[]>> computers, int start) {
        int[] time = new int[computers.size()];
        Arrays.fill(time, 100000001);
        time[start] = 0;

        PriorityQueue<int[]> queue = new PriorityQueue<>((int[] c1, int[] c2) -> c1[0] <= c2[0] ? 1 : -1);
        queue.offer(new int[]{0, start});

        while (!queue.isEmpty()) {
            int[] current = queue.poll();  // 0: current_time, 1: current_node

            if (current[0] > time[current[1]]) {
                continue;
            }

            for (int[] adj : computers.get(current[1])) {  // 0: adj, 1: time
                int dist = adj[1] + current[0];
                if (time[adj[0]] > dist) {
                    time[adj[0]] = dist;
                    queue.offer(new int[]{dist, adj[0]});
                }
            }
        }

        return time;
    }
}