[백준/Baekjoon] 1325 효율적인 해킹 C++ :: BFS

https://www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

---

1. Logic

- 모든 노드엗 대해 BFS를 돌며 해당 노드의 해킹 가능 컴퓨터 수를 cnt에 저장하고 벡터에 저장했다. 동시에 최대 해킹 대수또한 글로벌 변수로 지정하여 갱신해줬다.

- BFS를 다 돈 이후 오름차순 정렬을 하고 최대 해킹 대수와 일치하는 숫자의 노드를 출력해주었다.

 

2. 최적화

정답 제출을 했더니 정답처리 되었지만 시간이 너무 오래걸려서 최적화를 해보려고했다.

처음에는 BFS 함수 내에서 탐색이 끝나면 모든 노드를 정답 후보 vector에 넣었지만 최적화 후에는 최대 해킹 대수를 갱신하는 동시에 갱신하게 되면 다른 노드들은 정답에서 제외되기 때문에 정답 후보 vector에서 전부 지웠다.

 

 

 

---

2. Code

최적화 전

#include<bits/stdc++.h>

using namespace std;

int n, m;
vector<int> vec[10001];
vector<bool> vis(10001, false);
vector<pair<int, int>> answerCnt;
int maxCnt = -9761234;

int BFS(int n) {
    vis.assign(10001, false);

    int cnt = 0;
    queue<int> q;

    q.push(n);

    vis[n] = true;

    while(!q.empty()) {
        int cur = q.front();
        cnt++;
        q.pop();

        for(auto a : vec[cur]) {
            if(vis[a]) continue;
            vis[a] = true;
            q.push(a);
        }
    }

    answerCnt.push_back({n, cnt});

    return cnt;
}

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

    cin >> n >> m;

    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        vec[b].push_back(a);
    }

    for(int i = 1; i <= n; i++) {
        maxCnt = max(maxCnt, BFS(i));
    }

    sort(answerCnt.begin(), answerCnt.end());

    for(int i = 0; i < n; i++) {
        if(maxCnt == answerCnt[i].second) {
            cout << answerCnt[i].first << " ";
        }
    }
}

 

최적화 후

#include<bits/stdc++.h>

using namespace std;

int n, m;
vector<int> vec[10001];
vector<bool> vis(10001, false);
vector<pair<int, int>> answerCnt;
int maxCnt = -9761234;

int BFS(int n) {
    vis.assign(10001, false);

    int cnt = 0;
    queue<int> q;

    q.push(n);

    vis[n] = true;

    while(!q.empty()) {
        int cur = q.front();
        cnt++;
        q.pop();

        for(auto a : vec[cur]) {
            if(vis[a]) continue;
            vis[a] = true;
            q.push(a);
        }
    }

    if(maxCnt < cnt) {
        answerCnt.clear();
        answerCnt.push_back({n, cnt});
    }
    else if(maxCnt == cnt) {
        answerCnt.push_back({n, cnt});
    }

    return cnt;
}

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

    cin >> n >> m;

    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        vec[b].push_back(a);
    }

    for(int i = 1; i <= n; i++) {
        maxCnt = max(maxCnt, BFS(i));
    }

    sort(answerCnt.begin(), answerCnt.end());

    for(int i = 0; i < answerCnt.size(); i++) {
            cout << answerCnt[i].first << " ";
    }
}

 

 

---

 

 

3. Feedback

- 시간이 3612가 나와서 벡터 안에 있는 값을 assign으로 지우기도 하고 벡터 생성자를 선언하여 초기화도 해봤지만 똑같았다. 문제 자체의 조건을 계산하는데에서 시간이 조금 오래 걸리는 것 같다.