백준 1325번 [효율적인 해킹](C++) -yes6686- 티스토리

백준 문제 풀이: 1325 (효율적인 해킹)

---

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

문제 설명:

컴퓨터 n대가 있고, 각각 신뢰 관계를 가진다. 한 컴퓨터가 다른 컴퓨터를 신뢰하면, 해킹 시 신뢰하는 컴퓨터도 함께 해킹된다. 이때, 어떤 컴퓨터를 해킹했을 때 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터 번호를 모두 출력하라.

핵심 알고리즘: 역방향 그래프를 구성하여 각 정점에서 DFS를 수행하면서 자신을 도달할 수 있는 정점 개수를 카운팅. 가장 큰 개수에 해당하는 정점들을 우선순위 큐에 저장 후 출력.

---

문제 해결 코드

// DFS로 역방향 해킹 그래프 탐색
#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

int visited[10001];   // 방문 여부
int cnt = 0;          // 해킹 가능한 컴퓨터 수

vector<int> v[10001]; // 역방향 인접 리스트
priority_queue<int, vector<int>, greater<int>> pq;

void dfs(int x) {
    if (visited[x]) return;
    visited[x] = 1;
    cnt++;
    for (int i = 0; i < v[x].size(); i++) {
        int next = v[x][i];
        dfs(next);
    }
}

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

    int n, m;
    cin >> n >> m;

    // b가 a를 신뢰하면, 해킹 시 b → a 해킹 가능 (역방향 저장)
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        v[b].push_back(a);
    }

    int maxCnt = 0;

    for (int i = 1; i <= n; i++) {
        dfs(i);  // i번 컴퓨터에서 해킹 가능한 컴퓨터 수 탐색

        if (cnt > maxCnt) {
            while (!pq.empty()) pq.pop(); // 이전 결과 초기화
            maxCnt = cnt;
            pq.push(i);
        } else if (cnt == maxCnt) {
            pq.push(i);
        }

        memset(visited, 0, sizeof(visited));
        cnt = 0;
    }

    // 정답 출력 (오름차순)
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘: DFS를 통해 역방향으로 신뢰 관계를 따라 해킹 가능한 노드의 수를 계산.
• 구현 세부사항: 입력 시 v[b].push_back(a)로 역방향 신뢰 관계 구성. 모든 노드를 순회하며 DFS 수행 후 최대값 비교.
• 시간 복잡도 분석: O(n ⋅ (n + m)). 노드마다 DFS를 수행하며, 최대 n개의 DFS가 실행되고 각 DFS는 O(n + m) 시간.

---

결과

예시 입력:

5 4
3 1
3 2
4 3
5 3

출력: 1 2

3번 컴퓨터를 해킹하면 1, 2번도 해킹되고, 4, 5번에서 3번으로 도달할 수 있으므로 총 5개 중 1번과 2번이 가장 해킹 당하기 쉬운 컴퓨터입니다.

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