백준 10282 - 해킹

문제 설명

최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.

최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 여러 컴퓨터로 이루어진 그래프가 존재하고 특정 컴퓨터를 시작으로 바이러스가 감염된다.

이때, 감염되는 컴퓨터의 수와 최종적으로 걸리는 시간을 계산하는 것이다.

 

즉, 그래프를 순회하는 것이 핵심이다.

BFS를 사용하여 다익스트라와 유사하게 해결할 수 있다.

소요 시간이 짧은 순서대로 연결하며 연결가능한 모든 컴퓨터를 연결하면 된다.

struct cmp
{
    bool operator() (pair<int, int>& a, pair<int, int>& b)
    {
        return a.second > b.second;
    }
};

void BFS(vector<vector<pair<int, int>>>& adj)
{
    priority_queue<pair<int, int>, vector<pair<int,int>>, cmp> pq;
    vector<bool> visited(N + 1, false);
    pq.push({ C, 0 });

    int time = 0;
    int cnt = 0;

    while (!pq.empty())
    {
        auto [computer, sec] = pq.top();
        pq.pop();

        if (visited[computer]) continue;
        visited[computer] = true;

        time = max(time, sec);
        cnt++;

        for (auto [next, s] : adj[computer])
        {
            pq.push({ next, sec+s });
        }
    }

    cout << cnt << " " << time << "\n";
}

 

간선은 단방향 간선이기 때문에 지문을 유의하여 읽고 전처리를 해야 한다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

int T, N, D, C;

struct cmp
{
    bool operator() (pair<int, int>& a, pair<int, int>& b)
    {
        return a.second > b.second;
    }
};

void BFS(vector<vector<pair<int, int>>>& adj)
{
    priority_queue<pair<int, int>, vector<pair<int,int>>, cmp> pq;
    vector<bool> visited(N + 1, false);
    pq.push({ C, 0 });

    int time = 0;
    int cnt = 0;

    while (!pq.empty())
    {
        auto [computer, sec] = pq.top();
        pq.pop();

        if (visited[computer]) continue;
        visited[computer] = true;

        time = max(time, sec);
        cnt++;

        for (auto [next, s] : adj[computer])
        {
            pq.push({ next, sec+s });
        }
    }

    cout << cnt << " " << time << "\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> T;

    while (T-- > 0)
    {
        cin >> N >> D >> C;
        vector<vector<pair<int,int>>> adj(N + 1);
        
        for (int i = 0; i < D; i++)
        {
            int a, b, s;
            cin >> a >> b >> s;

            adj[b].push_back({ a,s });
        }

        BFS(adj);
    }

    return 0;
}

---