[BOJ알고리즘, C++]#10282_해킹, 길 찾기 알고리즘, 최단 경로 알고리즘, 다익스트라

 

#1. 문제

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

 

---

 

#2. 풀이

 

1. 다익스트라

[알고리즘]#2_길 찾기 알고리즘

다익스트라 알고리즘은 양의 가중치를 갖는 그래프에서 '단일 출발 최단 경로'를 구하는 길 찾기 알고리즘입니다. 일반적으로, 다익스트라 알고리즘은 하나의 출발 정점에 대하여 다른 모든 정점을 도착 정점으로 하는 최단 경로를 찾는 알고리즘으로, 우선순위 큐와 최단 경로 목록을 활용합니다. 주의할 점은 간선의 방향성 여부에 따라서 중복 업데이트 방지를 위해 각 정점의 방문 여부를 기록할 것인지 고려해야 합니다!

 

2. 감염에 걸리는 시간을 '가중치'로 보자!

1. 어떤 한 컴퓨터의 감염 시작 시간은 의존성이 있는 컴퓨터들 중 가장 먼저 감염이 시작된 컴퓨터로부터 영향을 받습니다. 따라서, 입력으로 주어진 '해킹당한 컴퓨터'를 출발 정점으로 다익스트라를 수행하며 마지막 컴퓨터가 감염되기까지 걸린 시간(최단 경로 값 중 최대 값을 갖는 정점)을 찾습니다!
2. 다익스트라를 정의합니다. 이 과정에서 최단 경로 값의 최대 값을 지속적으로 업데이트해줍니다.
3. 마지막으로, 최단 경로 값이 최대가 되는 정점과 그 값을 결과로 출력합니다.

 

---

 

#3. 코드

 

/*
    @문제 : 감염된 컴퓨터를 시작으로 전여된 총 컴퓨터 갯수와 마지막 컴퓨터가 감염되기 까지 걸린 시간
    @설명
            1. 단순히, bfs를 수행하며 마지막 컴퓨터가 감염되기 까지 걸린 시간을 찾으려고 했으나, 문제를 이해 못했다.
            2. 여러 컴퓨터에 의존성을 갖는 어떤 컴퓨터가 이미 '감염'된 순간부터, 더 이상 감염 피해를 받을 수 없다. 따라서, 해당 컴퓨터까지 "
            최단 경로", 즉 제일 빨리 감염시키는 루트를 찾는 것이다!
            3. 결국, BFS 대신 다익스트라를 활용했다.
*/

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

#define MAX 10001
typedef pair<int,int> p;

int T, n ,d, c;

void dijkstra(int start, vector<vector<p>>& graph)
{
    vector<int> infectedTime(n+1, INT_MAX);
    priority_queue<p, vector<p>, greater<p>> pq;
    int cnt = 0;
    int maxTime = 0;

    infectedTime[start] = 0;
    pq.push({0, start});

    while(!pq.empty())
    {
        int curTime = pq.top().first;
        int cur = pq.top().second;
        pq.pop();

        if(infectedTime[cur] < curTime) continue;

        cnt++;
        maxTime = max(maxTime, curTime);

        for(const auto& edge : graph[cur])
        {
            int next = edge.first;
            int newTime = curTime + edge.second;

            if(infectedTime[next] > newTime)
            {
                infectedTime[next] = newTime;
                pq.push({newTime, next});
            }
        }
    }

    cout << cnt << ' ' << maxTime << '\n';

}

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

    cin >> T;

    while(T--)
    {
        cin >> n >> d >> c;

        vector<vector<p>> graph(n+1);
        
        while(d--)
        {
            int a, b, s;
            cin >> a >> b >> s;

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

        // 다익스트라
        dijkstra(c, graph);

    }

    return 0;
}

 

---