Easy is Perfect

[백준] 2617번 C/C++ 풀이 _ 구슬 찾기

  • melonicedlatte
  • Nov 11, 2018


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

구슬 찾기

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초128 MB121338531035.187%

문제

모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 아 래와 같은 일을 하려 한다.

우리에게 주어진 것은 양팔 저울이다. 한 쌍의 구슬을 골라서 양팔 저울의 양쪽에 하나씩 올려 보면 어느 쪽이 무거운 가를 알 수 있다. 이렇게 M개의 쌍을 골라서 각각 양팔 저울에 올려서 어느 것이 무 거운 가를 모두 알아냈다. 이 결과를 이용하여 무게가 중간이 될 가능성이 전혀 없는 구슬들은 먼저 제외한다.

예를 들어, N=5이고, M=4 쌍의 구슬에 대해서 어느 쪽이 무거운가를 알아낸 결과가 아래에 있다.

  1. 구슬 2번이 구슬 1번보다 무겁다.
  2. 구슬 4번이 구슬 3번보다 무겁다.
  3. 구슬 5번이 구슬 1번보다 무겁다.
  4. 구슬 4번이 구슬 2번보다 무겁다.

위와 같이 네 개의 결과만을 알고 있으면, 무게가 중간인 구슬을 정확하게 찾을 수는 없지만, 1번 구슬과 4번 구슬은 무게가 중간인 구슬이 절대 될 수 없다는 것은 확실히 알 수 있다. 1번 구슬보다 무거운 것이 2, 4, 5번 구슬이고, 4번 보다 가벼운 것이 1, 2, 3번이다. 따라서 답은 2개이다.

M 개의 쌍에 대한 결과를 보고 무게가 중간인 구슬이 될 수 없는 구슬의 개수를 구하는 프로그램을 작성하시오.

입력

첫 줄은 구슬의 개수를 나타내는 정수 N(1 ≤ N ≤ 99)과 저울에 올려 본 쌍의 개수 M 이 주어진다. 그 다음 M 개의 줄은 각 줄마다 두 개의 구슬 번호가 주어지는데, 앞 번호의 구슬이 뒤 번호의 구슬보다 무겁다는 것을 뜻한다.

출력

첫 줄에 무게가 중간이 절대로 될 수 없는 구슬의 수를 출력 한다.

예제 입력 1 

5 4
2 1
4 3
5 1
4 2

예제 출력 1 

2

출처

Olympiad > 한국정보올림피아드 > KOI 2003 > 중등부 1번

알고리즘 분류

풀이

노드의 개수가 별로 많지 않습니다. 
일일히 모든 노드를 BFS로 탐색하면서 탐색한 노드의 자식의 개수를 모두 기록하고,
관계를 보면서 부모의 개수도 기록해줍니다.

자세한 풀이는 소스코드를 참조해주세요~

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <queue>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
vector<int> relation[100];
int is_visited[100], smaller_child[100], bigger_child[100];
 
int main() {
    int N, M; cin >> N >> M;
    int mid = (N + 1) / 2;
    // 관계 설정 
    for (int i = 0; i < M; ++i) {
        int big, small; cin >> big >> small;
        relation[big].push_back(small);
    }
 
    //각 번호 별로 자기부터 작은 것을 센다
    for (int i = 1; i <= N; ++i) {
        int child_num = 0, start = i;
        memset(is_visited, -1, sizeof(is_visited)); 
 
        // BFS 시작
        queue<int> que;     que.push(start);
        while (!que.empty()) {
            int now_node = que.front(); que.pop();
            int small_node_num = relation[now_node].size();
            for (int j = 0; j < small_node_num; ++j) {
                int child_node = relation[now_node][j]; 
                // 자신보다 큰 노드의 개수를 1 추가하고
                // 처음 BFS를 시작한 노드의 자식수 cnt 를 1 추가
                if (is_visited[child_node] == -1) {
                    bigger_child[child_node]++, child_num++;
                    is_visited[child_node] = 1;
                    que.push(child_node);
                }
            }
        }
        smaller_child[i] = child_num;  //자기보다 작은노드의 수 기록
    }
 
    int ans = 0;
    for (int i = 1; i <= N; ++i)
        if (bigger_child[i] >= mid || smaller_child[i] >= mid) ans++;
 
    cout << ans << endl;
    return 0;
}
cs



Search