BOJ 2617번: 구슬 찾기

문제 설명

무게가 중간이 될 수 없는 구슬의 개수 구하기

🔗 문제 링크

핵심 아이디어

• 정방향 그래프 (더 가벼운 구슬들), 역방향 그래프 (더 무거운 구슬들) 로 나눠서 입력받기
• BFS로 각 정점별로 연결된 구슬들의 개수를 세서 정방향/역방향 그래프들 중 하나라도 절반인 n/2보다 크면 중간 구슬이 아니라는 것!

코드

#include <bits/stdc++.h>
using namespace std;
int n, m, a, b;
vector<int> adj[105];
vector<int> rev[105];
int vis[105];

int bfs(int start, vector<int> graph[105]){
    fill(vis, vis + 105, 0);
    queue<int> q;
    q.push(start);
    vis[start] = 1;
    
    int cnt = 0;
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(auto nxt : graph[cur]){
            if (vis[nxt]) continue;
            vis[nxt] = 1;
            q.push(nxt);
            cnt++;
        }
    }
    return cnt;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a >> b;
        adj[a].push_back(b);
        rev[b].push_back(a);
    }
    
    int ans = 0;
    for(int i = 1; i <= n; i++){
        int ad = bfs(i, adj);
        int re = bfs(i, rev);
        if (ad > n/2 || re > n/2) ans++;
    }
    
    cout << ans;
}