[Algorithm]Baekjoon 2617번 :: 구슬 찾기

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
 
using namespace std;
 
int n, m;
vector<vector<int>> graph[2];
int updownCounts[2][101] = { 0 };
 
void BFS(int startNode, bool flag)
{
    bool visited[101] = { false };
    visited[startNode] = true;
    queue<int> q;
    q.push(startNode);
    
    while (!q.empty())
    {
        int curNode = q.front();
        q.pop();
 
        for (int i = 0; i < graph[flag][curNode].size(); ++i)
        {
            int nextNode = graph[flag][curNode][i];
            
            if (visited[nextNode]) continue;
 
            visited[nextNode] = true;
            ++updownCounts[flag][startNode];
            q.push(nextNode);
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
    
    if (n == 1)
    {
        cout << 0;
        return 0;
    }
 
    graph[0].resize(101);
    graph[1].resize(101);
 
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;
 
        graph[0][a].push_back(b);
        graph[1][b].push_back(a);
    }
 
    for (int i = 1; i <= n; ++i)
    {
        BFS(i, 0);
        BFS(i, 1);
    }
 
    int standard = n / 2;
    int answer = 0;
 
    for (int i = 1; i <= n; ++i)
    {
        if (updownCounts[0][i] > standard || updownCounts[1][i] > standard)
        {
            ++answer;
        }
    }
 
    cout << answer;
}
 
 

 

절대로 가운데무게가 될 수 없는 구슬의 개수를 구해야하는 문제.

 

특정구슬이 정확히 가운데무게가 되려면, 해당 구슬보다 무거운것, 가벼운것의 개수가 각각 n/2개가 되야한다.

그러니, 무거운개수든 가벼운개수든 한쪽이라도 개수가 유효하지 않으면 그것은 가운데 무게가 될 수 없다.

 

'확실하게' 아닌것을 구해야 하기 때문에, 한쪽방향이라도 n/2개를 넘어설 경우를 기준으로 한다.

탐색자체는 간단하게 BFS로 위,아래 탐색을 해줬다.