[Algorithm] BOJ 2617 구슬찾기

문제 링크

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

풀이

구슬의 무게에 대한 대소 정보가 주어졌을 때, 무게가 중앙값이 될 수 없는 구슬을 찾는 문제
무게가 중앙값이 되려면 자신보다 가벼운 구슬이 (n-1)/2개, 무거운 구슬이 (n-1)/2개 있어야 한다

무게 대소 정보를 그래프로 나타내고, 각 정점에서 BFS를 수행하면 연결 정보에 따라 해당 구슬보다 무게가 무겁거나 가벼운 구슬의 갯수를 구할 수 있다.

각 정점에서 구한 구슬의 갯수가 (n-1)/2개보다 크면 중앙값이 될 수 없으므로, 해당 구슬의 갯수를 카운팅해준다

코드

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

const int MAX = 100;

int n, m;
int answer = 0;
int visited[MAX];

int bfs(vector<vector<int>> &graph, int targetNode) {
    memset(visited, 0, sizeof(visited));

    queue<int> q;
    visited[targetNode] = 1;
    q.push(targetNode);

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

        for (auto nextNode : graph[cur]) {
            if (visited[nextNode]) continue;
            q.push(nextNode);
            visited[nextNode] = 1;
            cnt++;
        }
    }
    return cnt;
}

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

    cin >> n >> m;

    vector<vector<int>> in(n + 1);  // (u, v) : u > v
    vector<vector<int>> out(n + 1); // (u, v) : u < v

    for (int i=0; i<m; i++) {
        int u, v;
        cin >> u >> v;
        in[u].push_back(v);
        out[v].push_back(u);
    }

    int middle = (n-1)/2;
    for (int node=1; node<=n; node++) {
        int big = bfs(out, node);    // node 구슬보다 무거운 구슬의 갯수
        int small = bfs(in, node);   // node 구슬보다 가벼운 구슬의 갯수

        if (big > middle || small > middle) answer += 1;
    }

    cout << answer;

    return 0;
}