[백준] 10282 - 해킹

1. 문제

10282번: 해킹

2. 개요

컴퓨터 a가 b에 의존한다면, 컴퓨터 b가 감염된 후 일정 시간 뒤 a도 감염된다.

감염된 첫 컴퓨터와 컴퓨터간의 의존 관계가 주어졌을 때, 감염되는 컴퓨터의 개수와 마지막 감염까지 걸리는 시간을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

다익스트라를 이용하여 풀 수 있다.

감염까지 걸리는 시간을 기준으로 우선순위 큐에 넣어가면서 감염되지 않은 컴퓨터에 접촉할 때 카운트를 1씩 해준다. 이 때 방문처리 배열에 지금까지 걸린 시간을 갱신해나간다.

모든 감염처리를 완료한 후, 카운트와 방문 배열의 최댓값을 출력해주면 된다.

3-2. Python

import sys
import heapq

T = int(sys.stdin.readline())

for tc in range(T):
    n, d, c = map(int, sys.stdin.readline().split())

    graph = [[] for i in range(n+1)]
    visited = [-1 for i in  range(n+1)]

    for i in range(d):
        e, s, t = map(int, sys.stdin.readline().split())

        graph[s].append([t, e])

    q = [[0, c]]

    infSum = 0
    lastTime = 0

    while q:
        nowTime, nowCom = heapq.heappop(q)

        if visited[nowCom] != -1:
            continue

        visited[nowCom] = nowTime
        infSum += 1

        for nextTime, nextCom in graph[nowCom]:
            nextTime += visited[nowCom]

            if visited[nextCom] != -1:
                continue

            heapq.heappush(q, [nextTime, nextCom])

    print(infSum, max(visited))

3-3. C#

namespace boj_10282
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int T = int.Parse(sr.ReadLine());

            for (int tc = 0; tc < T; tc++)
            {
                string[] input = sr.ReadLine().Split();
                int n = int.Parse(input[0]), d = int.Parse(input[1]), c = int.Parse(input[2]);

                List<int[]>[] graph = new List<int[]>[n + 1];

                for (int i = 0; i < n + 1; i++)
                    graph[i] = new();

                int[] visited = new int[n + 1];
                Array.Fill(visited, -1);

                for (int i = 0; i < d; i++)
                {
                    input = sr.ReadLine().Split();
                    int e = int.Parse(input[0]), s = int.Parse(input[1]), t = int.Parse(input[2]);

                    graph[s].Add(new int[] { t, e });
                }

                PriorityQueue<int[], int> q = new();

                q.Enqueue(new int[] { 0, c }, 0);

                int infSum = 0;

                while (q.Count > 0)
                {
                    int[] now = q.Dequeue();
                    int nowTime = now[0], nowCom = now[1];

                    if (visited[nowCom] != -1)
                        continue;

                    visited[nowCom] = nowTime;
                    infSum++;

                    foreach (int[] nexts in graph[nowCom])
                    {
                        int nextTime = nexts[0], nextCom = nexts[1];
                        nextTime += visited[nowCom];

                        if (visited[nextCom] != -1)
                            continue;

                        q.Enqueue(new int[] { nextTime, nextCom }, nextTime);
                    }
                }

                sw.WriteLine($"{infSum} {visited.Max()}");
            }

            sw.Close();
        }
    }
}