• TOC {:toc}

이 글은 백준 온라인 저지의 10282번 문제를 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.07.07 (Python)

메모리 시간 코드 길이
48988 KB 888 ms 735 B
단계 시작 시각 끝난 시각 걸린 시간
문제 이해 15:54:20 15:57:05
풀이 생각 16:21:44 16:30:57
코딩 19:54:58 20:18:11
디버깅 1 20:27:05 20:29:47
디버깅 2 20:34:53 20:40:38 
import sys
from heapq import heappush, heappop
from math import isinf

input = sys.stdin.readline

for _ in range(int(input())):
    n, d, c = map(int, input().split())

    # 컴퓨터 간의 연결 관계
    net = [[] for _ in range(n + 1)]
    for _ in range(d):
        a, b, s = map(int, input().split())
        net[b].append((s, a))

    # 출발점에서 해당 컴퓨터까지 가는데 걸리 최소 시간
    # inf로 초기화 한다.
    sec = [float("inf")] * (n + 1)
    sec[c] = 0
    heap = [(0, c)]

    while heap:
        s_sec, s = heappop(heap)

        if sec[s] < s_sec:
            continue

        for x_sec, x in net[s]:
            total_sec = s_sec + x_sec
            if total_sec < sec[x]:
                sec[x] = total_sec
                heappush(heap, (total_sec, x))

    # sec 중 값이 inf가 아닌 값을 추려서
    res = [s for s in sec if not isinf(s)]
    # 그 개수와 최댓값을 출력한다.
    print(len(res), max(res))

아이디어 & 풀이

다익스트라 알고리즘을 이용해서 푼다.

  • 다익스트라 알고리즘은 [[wiki0:fc-algo-algorithm-20-shortest]]{강의 정리글}을 참고한다.
  • b에서 a로 갈 수 있기 때문에 연결 관계를 net[b] = [갈 수 있는 컴퓨터의 리스트]로 만든다.
  • 컴퓨터를 감염시키면 inf로 초기화된 값이 지금가지 지난 촛값으로 바뀌기 때문에 마지막에 sec중 inf 값을 갖지 않는 값을 추려내면 감염된 컴퓨터들만 남길 수 있다.

디버그

  • 두 번째 값을 max(res)를 출력해서 틀렸다.
    • 알고리즘 상 마지막에 감염시키는 컴퓨터까지 지난 초를 더해가기 때문에 res 값의 합이 아니라 최댓값을 구했어야 했다.
  • 메모리 초과가 계속 났다.
    • sec의 값과 다음 노드(i.e., x)를 감염시키는 데 걸리는 시간을 비교할 때 s_sec + x_sec인 total_sec와 sec(x)를 비교해야 하는데 x_sec와 비교해서 너무 많은 원소가 heap으로 들어가게 된 것 같다.

2022.04.08 (JS)

메모리 시간 코드 길이
133788 KB 1860 ms 1033 B
단계 시작 시각 끝난 시각 걸린 시간
문제 이해 21:41:49 21:43:57
풀이 생각 21:43:58 21:47:56
코딩 21:47:57 22:09:26 
const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

function dijkstra(graph, start, sec) {
    const queue = [start];

    while (queue.length) {
        const node = queue.shift();
        graph[node].forEach((comp) => {
            const [n, s] = comp;
            if (sec[node] + s < sec[n]) {
                sec[n] = sec[node] + s;
                queue.push(n);
            }
        });
    }
    const res = sec.filter((elem) => elem !== Infinity);
    console.log(res.length, Math.max(...res));
}

const [T, ...lines] = input;
let j = 0;

for (let i = 0; i < T; i += 1) {
    const [n, d, c] = lines[j].split(" ").map((n) => parseInt(n));
    const graph = Array(n + 1)
        .fill()
        .map((i) => []);

    for (let k = 0; k < d; k += 1) {
        const [a, b, s] = lines[j + k + 1].split(" ").map((n) => parseInt(n));
        graph[b].push([a, s]);
    }
    const sec = Array(n + 1).fill(Infinity);
    sec[c] = 0;

    dijkstra(graph, c, sec);

    j += d + 1;
}