[1325] 효율적인 해킹 (C++)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<vector<int>> A;
vector<bool> visited;
vector<int> cnt;
int max_visited = 0;

void BFS (int node);

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

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

    A.resize(n + 1);
    visited.resize(n + 1);
    cnt.resize(n + 1);
    
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        A[a].push_back(b);
    }

    for (int i = 0; i <= n; i++) {
        fill(visited.begin(), visited.end(), false);
        BFS(i);
    }

    for (int i = 1; i <= n; i++) {
        max_visited = max(max_visited, cnt[i]);
    }

    for (int i = 1; i <= n; i++) {
        if (cnt[i] == max_visited)
            cout << i << " ";
    }

    return 0;
}

void BFS(int node) {
    queue<int> Q;
    Q.push(node);
    visited[node] = true;

    while (!Q.empty()) {
        int now = Q.front();
        Q.pop();
        for (int i : A[now]) {
            if (visited[i] == false) {
                visited[i] = true;
                cnt[i] ++;
                Q.push(i);
            }
        }
    }
}

 

BFS의 응용 문제

1. 2차원 vector A를 선언해 각 컴퓨터가 신뢰하는 컴퓨터를 인접 리스트로 저장한다

2. 방문 여부를 체크하기 위한 vector visited와 신뢰받은 횟수를 저장하기 위한 vector cnt를 생성한다

3. 각 노드의 초기 visited 값을 false로 설정, 방문하면 true로 만들어준다

4. BFS에서는 FIFO 방식으로 탐색하기 위해 queue를 사용한다

5. 현재 노드에서 인접한 모든 노드에 대해 visited의 값이 false, 즉 방문하지 않았다면 queue에 삽입한다

6. queue에 삽입함과 동시에 해당 노드의 cnt 값을 증가시켜준다

7. max_visited의 초기값을 0으로 설정하고, cnt와 차례대로 비교하며 신뢰받은 횟수의 최대값을 저장한다

8. max_visited에 저장된 신뢰받은 횟수의 최대값과 일치하는 컴퓨터의 번호를 출력한다