백준 10282번 - 해킹

해킹 문제 바로 가기

풀이 날짜: 2026-06-15

baekjoon 알고리즘 문제 풀이

풀이 코드


import heapq
t = int(input())
for _ in range(t):

    n,d,c = map(int, input().split())
    INF = int(1e9)
    graph = [[] for _ in range(n+1)]
    distance = [INF] * (n+1)

    for _ in range(d):
        a,b,s = map(int, input().split())
        graph[b].append((a,s))

    def dijkstra(start):
        q = []
        heapq.heappush(q,(0,start))
        distance[start] = 0

        while q:
            dist, now = heapq.heappop(q)

            if distance[now] < dist:
                continue

            for next_node, fee in graph[now]:
                cost = dist + fee
                if cost < distance[next_node]:
                    distance[next_node] = cost
                    heapq.heappush(q,(cost,next_node))

    dijkstra(c)

    count = 0
    time = 0

    for i in distance:
        if i != INF:
            count += 1
            time = max(time,i)

    print(count, time)

접근 방법

이 문제는 해킹이 발생한 컴퓨터로부터 다른 컴퓨터들이 감염되는 과정을 시간 순서대로 계산해야 한다. 각 컴퓨터 간의 의존 관계와 감염 시간을 고려하여 가장 빠르게 감염되는 시간을 구해야 하므로 최단 경로 문제로 변환할 수 있다. 시작 컴퓨터로부터 각 컴퓨터까지의 최소 감염 시간을 구하기 위해 다익스트라 알고리즘을 사용하였다.

그래프 구성

입력으로 주어지는 a b s는 “컴퓨터 b가 감염되면 s초 후 컴퓨터 a가 감염된다”는 의미이다. 일반적인 방향 그래프 문제와 다르게 의존 관계가 반대로 주어지므로 그래프를 구성할 때 방향을 뒤집어 저장해야 한다.

graph[b].append((a, s))

다익스트라 알고리즘 적용

시작 컴퓨터 c를 기준으로 우선순위 큐를 이용한 다익스트라 알고리즘을 수행하였다. 큐에서 현재까지 가장 짧은 시간이 기록된 컴퓨터를 꺼내고, 연결된 컴퓨터들의 감염 시간을 갱신하였다. 이미 더 짧은 시간이 기록되어 있는 경우에는 탐색을 생략하여 불필요한 연산을 줄였다.

결과 계산

다익스트라 수행이 끝난 후 거리 배열을 순회하면서 감염 여부를 확인하였다. 최단 거리가 INF가 아닌 경우는 감염된 컴퓨터를 의미하므로 개수를 세었고, 감염 시간 중 가장 큰 값을 마지막 감염 시간으로 저장하였다.

배운 점

이 문제의 핵심은 입력으로 주어지는 의존 관계의 방향을 정확히 해석하는 것이었다. 처음에는 a → b 형태로 그래프를 구성하기 쉽지만 실제로는 b → a 방향으로 저장해야 한다. 또한 감염 시간이 누적되는 과정을 최단 경로 문제로 변환할 수 있다는 점에서 다익스트라 알고리즘의 대표적인 응용 문제라는 것을 확인할 수 있었다. 특히 최단 거리 배열에서 INF 여부만으로 감염된 컴퓨터 수를 구할 수 있다는 점도 함께 익힐 수 있었다.

Vienna sausage