[BOJ / C++] 구슬 찾기 (그래프)

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

 

1. 코드

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

int bfsCnt(int n, vector<vector<int>>& adj, int st) {
    vector<bool> vis(n+1, false);
    queue<int> Q;

    Q.push(st);
    vis[st] = true;
    int cnt = 0;

    while (!Q.empty()) {
        int cur = Q.front(); Q.pop();
        for (int nxt : adj[cur]) {
            if (vis[nxt]) continue;
            Q.push(nxt);
            vis[nxt] = true;
            cnt++;
        }
    }

    return cnt;
}

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

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

    vector<vector<int>> adj_light(n+1);
    vector<vector<int>> adj_heavy(n+1);

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

        adj_light[a].push_back(b);
        adj_heavy[b].push_back(a);
    }

    int exclude = 0;

    // light 탐색
    for (int i = 1; i < n+1; i++) {
        if (bfsCnt(n, adj_light, i) > (n/2)) exclude++;
    }

    // heavy 탐색
    for (int i = 1; i < n+1; i++) {
        if (bfsCnt(n, adj_heavy, i) > (n/2)) exclude++;
    }

    cout << exclude;
}

 

 

2. 시간복잡도

인접리스트에서 BFS 순회는 O(v+e)이다. n = 99, m = 5,000이고 모든 정점에서 BFS를 해야하므로 O(v * (v+e)) = 100 * 5100 < 10^8 이므로 시간제한 1초내에 통과 가능하다.

 

 

3. 분석

 

무거운 것을 adj_heavy, 가벼운 것을 adj_light에 따로 그래프 정보를 저장하고 노드마다 BFS로 연결 노드 개수를 세서 cnt > n/2이면 중심에 올 수 없다라고 하는 아이디어를 떠올려야했다. 이 부분이 참신했다. 무거운 것과 가벼운 것을 따로 그래프를 나눠서 정보를 저장할 수도 있었다.