[C++] 백준/Silver/1325. 효율적인 해킹

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

문제 분석

N개의 컴퓨터와 M개의 신뢰 관계가 주어질 때, 한 컴퓨터를 해킹하면 그 컴퓨터를 신뢰하는 다른 컴퓨터들도 해킹할 수 있다.
각 컴퓨터를 시작점으로 하여 해킹할 수 있는 컴퓨터의 수(직접 및 간접)를 구한 뒤, 가장 많은 컴퓨터를 해킹할 수 있는 노드를 출력하는 문제이다.

 

접근
입력으로 주어지는 (a, b) 관계는 "a가 b를 신뢰한다"는 의미이므로,
b를 해킹하면 a도 해킹할 수 있다.
이를 위해, 각 노드에 대해 역방향 그래프를 구성하여, 해당 노드에서 출발해 도달할 수 있는 노드의 수를 구하면 된다.

---

해결 방법

그래프 구성:

• 입력 (a, b)를 받으면, graph[b]에 a를 추가한다.
  → 이렇게 하면 b를 해킹했을 때, a로 확산되는 효과를 모사할 수 있다.

BFS 탐색:

• 각 노드 i(1 ≤ i ≤ N)에 대해 BFS를 수행하여,
  i를 시작점으로 해킹할 수 있는 컴퓨터의 수를 구한다.
• 방문 여부를 기록하여 중복 방문을 방지한다.

최대 해킹 가능 수:

• 모든 노드에 대해 해킹 가능 컴퓨터의 수를 구한 후,
  최대 값(maxCnt)을 갱신한다.
• 이후 최대 해킹 가능 수를 가진 노드들을 출력한다.

코드 전체

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0);
    
    int n, m; 
    cin >> n >> m;
    // 역방향 그래프: graph[b]에 a를 저장 (a가 b를 신뢰)
    vector<vector<int>> graph(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b; 
        cin >> a >> b;
        graph[b].push_back(a);
    }
    
    vector<int> result(n + 1); // 각 노드에서 해킹 가능한 컴퓨터 수
    int maxCnt = 0;
    
    // 모든 컴퓨터를 시작점으로 BFS 실행
    for (int i = 1; i <= n; i++) {
        vector<bool> visited(n + 1, false);
        queue<int> bfs;
        bfs.push(i);
        visited[i] = true;
        int count = 0;
        
        while (!bfs.empty()) {
            int node = bfs.front();
            bfs.pop();
            count++;
            for (const int& next : graph[node]) {
                if (visited[next]) continue;
                visited[next] = true;
                bfs.push(next);
            }
        }
        result[i] = count;
        maxCnt = max(maxCnt, count);
    }
    
    // 최대 해킹 가능한 컴퓨터 수를 가진 모든 노드 출력
    for (int i = 1; i <= n; i++) {
        if (result[i] == maxCnt)
            cout << i << ' ';
    }
    
    return 0;
}