백준 g4 2617 구슬 찾기 c++

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

2617번: 구슬 찾기

 

문제

각각 무게가 다른 구슬 N개가 주어지고, M개의 구슬 2개 간의 대소 관계가 주어진다.

이때 구슬 무게의 중앙값을 찾으려고 한다. M개의 대소 관계가 주어지면 중앙값이 절대로 될 수 없는 구슬들을 알 수 있다. 중앙값이 절대로 될 수 없는 구슬들의 개수는?

 

예제

2>1

4>3

5>1

4>2

가 주어지면, 1보다 큰 구슬이 2, 4, 5로 3개이므로 1은 중앙값이 될 수 없다.

마찬가지로 4보다 작은 구슬이 1, 2, 3으로 3개이므로 4 역시 중앙값이 될 수 없다.

 

풀이

그래프 단원 문제가 아니었다면 아마 그래프 풀이를 떠올리기 어려웠을 문제

각 숫자들의 연쇄적인 대소 관계를 알아야 하며 그 개수를 세야 한다.

 

그래프로 한 무게보다 작은 게 몇 개인지, 큰 게 몇 개인지 BFS로 개수를 찾으면 된다.

이때 그래프를 무방향 그래프로 하면 대소 관계가 맞지 않기 때문에 방향이 있는 그래프로 설정해주어야 한다.

ex.

1 -> 2 -> 4

1 -> 5

의 경우에 무방향 그래프로 하면 4보다 확실하게 작은 수가 1, 2, 5 3개가 된다.

 

예제에서 1같이 1보다 큰 수를 구하기 위한 인접 리스트 adj,

예제에서 4같이 4보다 작은 수를 구하기 위한 인접 리스트 r_adj 2개를 둬서 두번씩 BFS를 돌리면 된다.

 

전체 코드

/*boj g4 2617 구슬 찾기*/
#include <iostream>
#include <queue>
#include <vector>
#define MAXN 101
using namespace std;

int N, M;

vector<int> adj[MAXN];
vector<int> r_adj[MAXN];
int vis[MAXN];
int BFS(vector<int> *vec, int start) {
    for (int i = 0; i < MAXN; i++)
        vis[i] = 0;

    queue<int> Q;
    Q.push(start);
    vis[start] = 1;
    int res = 0;

    while (!Q.empty()) {
        int cur = Q.front();
        Q.pop();

        for (int a : vec[cur]) {
            if (vis[a]) continue;

            Q.push(a);
            vis[a] = vis[cur] + 1;
            res++;
        }
    }
    return res;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;

    while (M--) {
        int x, y;
        cin >> x >> y;

        adj[y].push_back(x);
        r_adj[x].push_back(y);
    }

    // BFS, adj와 r_adj의 개수 세기, 만약 한 쪽의 개수가 (N+1)/2이상이면 불가능
    int answer = 0;
    for (int i = 1; i <= N; i++) {
        if (BFS(adj, i) >= (N + 1) / 2) {
            answer++;
            continue;
        } else if (BFS(r_adj, i) >= (N + 1) / 2) {
            answer++;
            continue;
        }
    }

    cout << answer << "\n";
}