[백준] 1325번 효율적인 해킹

문제: 1325번: 효율적인 해킹

basic-algo-lecture/workbook/0x18.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x18.md at master · encrypted-def/basic-algo-lecture

 

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> graph;
vector<bool> check;

int BFS(int start) {
    int tmpCnt = 0;

    queue<pair<int, int>> nexts;
    nexts.push({ start, 1 });
    check[start] = 1;

    while (!nexts.empty()) {
        pair<int, int> cur = nexts.front(); nexts.pop();
        tmpCnt++;
    
        for (int next : graph[cur.first]) {
            if (check[next]) continue;

            nexts.push({ next, cur.second + 1 });
            check[next] = 1;
        }
    }
    return tmpCnt;
}

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

    int n, m; // 학생 수, 신뢰 관계 수
    cin >> n >> m;
    graph = vector<vector<int>>(n + 1); // 0번 인덱스 안 써용
    check = vector<bool>(n + 1);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b; // a 가 b 를 신뢰함

        graph[b].push_back(a);
    }
    int curMax = -1;
    vector<int> answerNums;
    // 흠.. 그냥 모든 정점을 돌면서, 기준으로 삼아가지고 BFS 돌리면 되는거 아님?
    for (int i = 1; i <= n; i++) {
        fill(check.begin(), check.end(), false); // 초기황

        int target = i;
        int tmpCnt = BFS(target);

        if (tmpCnt >= curMax) {
            if (tmpCnt > curMax) {
                curMax = tmpCnt;
                answerNums.clear();
            }
            answerNums.push_back(target);
        }
    }
    sort(answerNums.begin(), answerNums.end());
    for (int ans : answerNums) cout << ans << " ";

    return 0;
}

 

처음에 BFS 함수에서 tmpCnt 값을 갱신할 때 tmpCnt = (tmpCnt < cur.second) ? cur.second : tmpCnt; 이렇게 해서 틀렸다. 이렇게 하면 최종적으로 연결된 모든 노드를 다 반영하지 못하는 문제가 있었따. 그래서 그냥 while 문 돌 때마다 tmpCnt++ 하도록 했더니 맞았다. 처음에는 중복되는 경우를 생각해서 짰던 거였는데 생각해보니까 코드에서 이미 조건문으로 check[next] 가 true 인 경우에 넘기도록 해서 중복되는 경우가 없는 경우였다. 그냥 단순히 tmpCnt++ 해주면 되는거였다. -_-