문제 출처

1. 문제설명

  • 구슬 두 개의 관계가 주어진다.
  • 입력으로 주어진 p가 c보다 무겁다는 뜻이다.
  • 이러한 관계가 주어졌을 때 중간이 될 가능성이 없는 구슬의 개수를 구하라


2. 알고리즘 설계

  • 그래프 문제이다.
  • 무거운 인접만 담은 그래프와 가벼운 인접만을 담은 그래프를 별도로 준비한다.
    • 이전 그래프 문제에서는 graph[u][v] = graph[v][u] = input 이었다.
  • 각각의 그래프를 편의상 adj_h(heavy), adj_l(light)라고 칭했다.
  • 각 그래프는 단방향 그래프가 된다. (무거운 쪽이거나 가벼운 쪽이거나)
  • 그래프 두개를 각각 BFS하고, 만약 인접한 노드의 개수가 전체 노드의 절반을 넘어서면 중간이 될 가능성이 없다.


3. 전체 코드

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

int n, m, p, c, ans;
vector<int> adj_h[100];
vector<int> adj_l[100];

bool solve(int start, vector<int> adj[]) {
    vector<bool> vis(n+1, false);
    
    queue<int> q;
    q.push(start);
    vis[start] = true;

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

        for(int nxt : adj[cur]) {
            if(!vis[nxt]) {
                vis[nxt] = true;
                q.push(nxt);
                cnt++;
            }
        }
    }

    return cnt >= (n + 1)/2;
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    while(m--) {
        cin >> p >> c;
        adj_h[p].push_back(c);
        adj_l[c].push_back(p);
    }

    for(int i=1; i<=n; i++)
        ans += (solve(i, adj_h) || solve(i, adj_l));
    cout << ans;

    return 0;
}