# [Gold IV] 구슬 찾기 #### [문제 링크](https://www.acmicpc.net/problem/2617) ## 문제 설명 <p>모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 아래와 같은 일을 하려 한다.</p> <p>우리에게 주어진 것은 양팔 저울이다. 한 쌍의 구슬을 골라서 양팔 저울의 양쪽에 하나씩 올려 보면 어느 쪽이 무거운가를 알 수 있다. 이렇게 M개의 쌍을 골라서 각각 양팔 저울에 올려서 어느 것이 무거운가를 모두 알아냈다. 이 결과를 이용하여 무게가 중간이 될 가능성이 전혀 없는 구슬들은 먼저 제외한다.</p> <p>예를 들어, N=5이고, M=4 쌍의 구슬에 대해서 어느 쪽이 무거운가를 알아낸 결과가 아래에 있다.</p> <ol> <li>구슬 2번이 구슬 1번보다 무겁다.</li> <li>구슬 4번이 구슬 3번보다 무겁다.</li> <li>구슬 5번이 구슬 1번보다 무겁다.</li> <li>구슬 4번이 구슬 2번보다 무겁다.</li> </ol> <p>위와 같이 네 개의 결과만을 알고 있으면, 무게가 중간인 구슬을 정확하게 찾을 수는 없지만, 1번 구슬과 4번 구슬은 무게가 중간인 구슬이 절대 될 수 없다는 것은 확실히 알 수 있다. 1번 구슬보다 무거운 것이 2, 4, 5번 구슬이고, 4번 보다 가벼운 것이 1, 2, 3번이다. 따라서 답은 2개이다.</p> <p>M 개의 쌍에 대한 결과를 보고 무게가 중간인 구슬이 될 수 없는 구슬의 개수를 구하는 프로그램을 작성하시오.</p> ## 입력 <p>첫 줄은 구슬의 개수를 나타내는 정수 N(1 ≤ N ≤ 99)과 저울에 올려 본 쌍의 개수 M(1 ≤ M ≤ N(N-1)/2)이 주어진다. 그 다음 M 개의 줄은 각 줄마다 두 개의 구슬 번호가 주어지는데, 앞 번호의 구슬이 뒤 번호의 구슬보다 무겁다는 것을 뜻한다.</p> ## 출력 <p>첫 줄에 무게가 중간이 절대로 될 수 없는 구슬의 수를 출력 한다.</p> ## 풀이 #### 문제에서는 중간 무게가 될 수가 없는 구슬의 수를 찾으라고 합니다. 이는 구슬의 무게의 최소 순위와 최대 순위를 찾아서 확인하면 됩니다. #### dfs나 bfs로 순방향 간선으로 한번, 역방향 간선으로 한번 순회하면 최소 위치와 최대 위치를 찾을 수 있습니다. 아래 코드에서는 bfs를 사용했습니다. #### 처음에는 dfs로 구현을 했지만, 이 문제에서 중복 간선이 들어온다는 사실을 고려하지 못했기 때문에 이틀동안 10<span style="color: red;">WA</span>를 받았습니다. ``` c++ #include<bits/stdc++.h> using namespace std; bool visited[99]; // 이미 방문한 위치인지 확인 vector<vector<int>> conn1(99); // conn1[A][B]: B가 A보다 무겁다. vector<vector<int>> conn2(99); // conn2[A][B]: A가 B보다 무겁다. int bfs(vector<vector<int>> conn, int cur) { int cnt=1; memset(visited, 0, sizeof visited); queue<int> q; q.push(cur); visited[cur]=true; while(!q.empty()) { cur = q.front(); q.pop(); for(int next:conn[cur]) { if(!visited[next]) { q.push(next); visited[next]=true; cnt++; } } } return cnt; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; while(m--) { int a, b; cin >> a >> b; conn1[b-1].push_back(a-1); conn2[a-1].push_back(b-1); } int cnt=0; for(int i=0;i<n;i++) { memset(visited, 0, sizeof visited); int sum1 = bfs(conn1, i); // i가 앞에서 최소 몇번째 위치하는지 memset(visited, 0, sizeof visited); int sum2 = bfs(conn2, i); // i가 뒤에서 최소 몇번째 위치하는지 // 중간 무게가 될 수 없는 경우 확인 if(!(sum1<=(n+1)/2 && (n+1)/2<=n-sum2+1)) cnt++; } cout << cnt; } ```