[C++] 백준/BOJ - 10282 : 해킹

---

문제 이해 단계

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

10282번: 해킹

A가 B에 의존하면, B가 감염됐을 때 A도 감염된다.
이를 의존이라고 한다.

입력으로 테스트 케이스 T, 컴퓨터 개수 n,
의존성 관계 개수 d, 해킹당한 컴퓨터의 번호 c가 주어진다.

의존성 관계 정보는 (a, b, s)로 주어지는데
이는 컴퓨터 a가 컴퓨터 b를 의존하고, b가 감염된 후 s초 후 컴퓨터 a도 감염된다는 뜻이다.

해당 조건일 때 출력으로 컴퓨터 수,
마지막 컴퓨터가 감염되는 데 걸리는 시간을 출력하는 문제

 

---

문제 접근 단계

문제 조건부터 살펴보면 컴퓨터의 개수 n은 최대 10,000개.
의존성 d는 최대 100,000개이다.

10^4 * 10^5 = 10^9로 시간초과가 나는 것에 유의하면서 문제를 풀어야 한다.
또한 해당 문제에서는 걸리는 시간을 구해야 하기 때문에 시간의 최댓값도 중요하다.

정수 s의 최대가 1,000인데, 이게 100,000개까지 가능하니까
10^3 * 10^5 = 10^8이라는 것에  유의하면서 풀어야 한다.

---

답을 구하는 과정

답을 구하는 과정을 한번 살펴보자.

일단 이 문제에서는 의존성이라는 단어를 썼는데,
이는 a와 b가 단방향성으로 연결되어 있다는 의미로 해석할 수 있다.

그리고 a에서 b로 가는데 s라는 시간이 걸린다.
이를 비용이 s가 든다라고 생각해 보자.

이는 가중치가 있는 그래프 문제와 비슷해 보인다.

문제에서 준 예제 입력을 한번 보자.

예제 입력 1에서 두번째 예제케이스

화살표는 의존성이 아니라 감염되는 방향을 나타낸다.

예를 들어, 1번이 감염되면 8초 뒤에 3번이 감염된다는 소리이다.

1번이 감염된 컴퓨터이기 때문에 2번과 3번도 동시에 감염이 진행된다.
그럼 2번은 2초 뒤, 3번은 8초 뒤에 감염이 된다.

 

2초 뒤 2번이 먼저 감염이 됐다.

2번이 2초 뒤에 감염이 먼저 됐다.
2번이 감염됐기 때문에 의존성에 의해 4초 뒤에 3번이 감염된다.

 

그럼 다시 4초 뒤(전체적으론 6초 뒤)에 3번이 감염됐다.

그렇게 1번이 감염될 때, 연관된 컴퓨터가 감염되는 데 걸리는 시간은 6초로 됐다.

여기서 맨 처음에 진행됐던 8초는
1번 -> 2번 -> 3번보다 느리기 때문에 사라졌다.

여기서 나는 이번 문제에서 구해야 하는 것이
"감염된 컴퓨터 c에서 갈 수 있는 컴퓨터들을 가장 짧은 시간을 써서 탐색하는 것"
이 문제의 핵심이라고 생각했다.

이 문제는 한 노드 c에서 출발해서
각 노드로 가는 가장 짧은 거리를 찾는 문제이다.

여기서 쓸 수 있는 가장 적절한 알고리즘이 바로 다익스트라 알고리즘이다.

다익스트라 알고리즘
하나의 정점에서 다른 정점으로 가는 최단거리를 구하기 위해 있는 알고리즘.

그래서 이 알고리즘을 적용하면 이 문제를 풀 수 있다.

다익스트라 알고리즘에 대해서는
내가 생각하기에 가장 쉽게 설명했다고 느끼는 동빈나 님의 블로그를 링크해 두겠다.

https://blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘

이제 자세한 풀이는 문제 구현 단계에서 하도록 하자.

 

---

문제 구현 단계

// 노드의 정보를 담는 벡터 (v[의존성을 받는 컴] = (시간,의존성 컴))
vector<pair<int,int>> v[100001]; 
int dp[100001]; // 각 노드의 최소 시간을 담는 dp 배열
int n,d,c;

// 다익스트라 알고리즘
void dijkstra(int x){
    // 우선순위 큐 (내림차순 정렬) 꺼낼 때, 시간을 기준으로 작은 것부터 꺼내짐
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
    dp[x] = 0; // 자기 자신의 시간을 0으로 설정
    q.push(make_pair(0,x)); // 큐에 넣음


    while(!q.empty()){
        int cnt = q.top().second; // 현재 노드
        int t = q.top().first; // 현재 시간
        q.pop();
        for(int i = 0; i < v[cnt].size(); i++){
            int next = v[cnt][i].second; // 다음 노드
            int nextTime = v[cnt][i].first + t; // 현재 시간 + 가는 시간
            // 저장되어있는 시간보다 작아야만 갱신
            if(nextTime < dp[next]){
                dp[next] = nextTime;
                q.push(make_pair(nextTime,next)); // 큐에 담음
            }
        }
    }

    // 개수 
    int com = 0, t = 0;
    for(int i = 1; i <= n; i++){
        if(dp[i] == INT32_MAX) continue;
        com++;
        t = max(t,dp[i]);
    }
    cout << com << " " << t << "\n";
    
}

dp 배열 안에 각 노드의 최소시간을 담는다.
그리고 우선순위 큐를 내림차순으로 정렬하여 시간이 적은 것부터 나오도록 한다.

이후의 답을 구하는 것은 컴퓨터 c와 아예 관계가 없어
값이 변하지 않은 것을 제외하고, 값이 다 변한 것만 세어서 감염된 컴퓨터의 수를 구한다.

또한 dp는 각 노드로 도착한 값인데,
이게 누적합이기 때문에 그중에서 가장 큰 값만 호출한다.

풀이는 여기까지고 아래에 전체 코드를 올리고 끝내겠다.

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

// 노드의 정보를 담는 벡터 (v[의존성을 받는 컴] = (시간,의존성 컴))
vector<pair<int,int>> v[100001]; 
int dp[100001]; // 각 노드의 최소 시간을 담는 dp 배열
int n,d,c;

// 다익스트라 알고리즘
void dijkstra(int x){
    // 우선순위 큐 (내림차순 정렬) 꺼낼 때, 시간을 기준으로 작은 것부터 꺼내짐
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
    dp[x] = 0; // 자기 자신의 시간을 0으로 설정
    q.push(make_pair(0,x)); // 큐에 넣음


    while(!q.empty()){
        int cnt = q.top().second; // 현재 노드
        int t = q.top().first; // 현재 시간
        q.pop();
        // 최단거리가 아닐 경우엔 굳이 안해도 됨
        if(dp[cnt] < t) continue;
        for(int i = 0; i < v[cnt].size(); i++){
            int next = v[cnt][i].second; // 다음 노드
            int nextTime = v[cnt][i].first + t; // 현재 시간 + 가는 시간
            // 저장되어있는 시간보다 작아야만 갱신
            if(nextTime < dp[next]){
                dp[next] = nextTime;
                q.push(make_pair(nextTime,next)); // 큐에 담음
            }
        }
    }

    // 개수 
    int com = 0, t = 0;
    for(int i = 1; i <= n; i++){
        if(dp[i] == INT32_MAX) continue;
        com++;
        t = max(t,dp[i]);
    }
    cout << com << " " << t << "\n";
    
}
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

    int T;
    cin >> T;
    while(T--){
        cin >> n >> d >> c;
        fill(dp,dp+100001,INT32_MAX);
        for(int i = 0; i <= 100000; i++) v[i].clear();
        for(int i = 0; i < d; i++){
            int v1,v2,v3;
            cin >> v1 >> v2 >> v3;
            v[v2].push_back(make_pair(v3,v1)); // (시간,컴퓨터)
        }
        dijkstra(c);
    }
}

 

---

시행착오

다익스트라 이해한다고 한참 걸렸다.
솔직히 아직도 알쏭달쏭한데, 잘 모르겠다.

나중에 비슷한 문제가 한번 더 나오고,
다익스트라인걸 눈치채고 다시 풀어봐야 할 것 같다..

아직까지 어렵다 알고리즘.. 쉽지가 않다..

https://toss.me/howudong

howudong님에게 보내주세요