백준 10282번 [해킹](C++) -yes6686- 티스토리

백준 문제 풀이: 10282 [해킹]

---

문제 링크: https://www.acmicpc.net/problem/10282

문제 설명:

한 컴퓨터가 해킹되면 의존 관계에 있는 다른 컴퓨터들로 해킹이 전파됩니다. 이 문제에서는 해킹이 시작된 컴퓨터로부터 다른 컴퓨터들까지 영향을 받는 데 걸리는 시간을 계산합니다.

• 의존 관계가 방향 그래프로 주어집니다.
• 다익스트라 알고리즘을 이용해 해킹 전파 시간과 영향을 받는 컴퓨터 수를 계산합니다.

---

문제 해결 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 1e9
using namespace std;

vector<pair<int, int>> graph[10001]; // 의존 관계를 저장하는 그래프
int distanceArr[10001]; // 각 컴퓨터까지의 최소 시간
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

void dijkstra(int start) {
    distanceArr[start] = 0;
    pq.push({0, start}); // 시작 컴퓨터로 가는 시간은 0

    while (!pq.empty()) {
        int cost = pq.top().first;
        int current = pq.top().second;
        pq.pop();

        for (auto [nextCost, next] : graph[current]) {
            if (distanceArr[next] > cost + nextCost) {
                distanceArr[next] = cost + nextCost;
                pq.push({distanceArr[next], next});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T; // 테스트 케이스 수
    cin >> T;

    while (T--) {
        int n, d, c; // 컴퓨터 수, 의존 관계 수, 해킹 시작 컴퓨터
        cin >> n >> d >> c;

        // 초기화
        for (int i = 1; i <= n; i++) {
            distanceArr[i] = INF;
            graph[i].clear();
        }

        // 의존 관계 입력
        for (int i = 0; i < d; i++) {
            int a, b, s;
            cin >> a >> b >> s;
            graph[b].push_back({s, a}); // b → a로 전파, 가중치는 s
        }

        // 다익스트라 알고리즘 수행
        dijkstra(c);

        // 결과 계산
        int count = 0; // 영향을 받은 컴퓨터 수
        int maxTime = 0; // 가장 오래 걸린 시간

        for (int i = 1; i <= n; i++) {
            if (distanceArr[i] != INF) {
                count++;
                maxTime = max(maxTime, distanceArr[i]);
            }
        }

        // 결과 출력
        cout << count << ' ' << maxTime << '\n';
    }

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 다익스트라 알고리즘을 사용해 해킹 전파 시간을 계산합니다. 방향 그래프에서 특정 시작 노드로부터 다른 노드까지의 최소 시간을 구합니다.
• 구현 세부사항:
  • distanceArr[i]: i번 컴퓨터까지의 최소 시간
  • graph[b].push_back({s, a}): 의존 관계를 방향성에 맞게 저장
  • 다익스트라 알고리즘으로 각 노드까지의 최소 시간을 업데이트
• 시간 복잡도 분석: O((n + d) log n)
  • n: 컴퓨터 수 (노드 수)
  • d: 의존 관계 수 (간선 수)
  • 우선순위 큐를 사용한 다익스트라 알고리즘의 시간 복잡도

---

결과

해킹 전파 시간과 영향을 받은 컴퓨터 수를 정확히 계산합니다. 다익스트라 알고리즘을 활용해 효율적으로 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!