출처 : https://www.acmicpc.net/problem/2617
구슬 찾기
시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 1213 | 385 | 310 | 35.187% |
문제
모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 아 래와 같은 일을 하려 한다.
우리에게 주어진 것은 양팔 저울이다. 한 쌍의 구슬을 골라서 양팔 저울의 양쪽에 하나씩 올려 보면 어느 쪽이 무거운 가를 알 수 있다. 이렇게 M개의 쌍을 골라서 각각 양팔 저울에 올려서 어느 것이 무 거운 가를 모두 알아냈다. 이 결과를 이용하여 무게가 중간이 될 가능성이 전혀 없는 구슬들은 먼저 제외한다.
예를 들어, N=5이고, M=4 쌍의 구슬에 대해서 어느 쪽이 무거운가를 알아낸 결과가 아래에 있다.
- 구슬 2번이 구슬 1번보다 무겁다.
- 구슬 4번이 구슬 3번보다 무겁다.
- 구슬 5번이 구슬 1번보다 무겁다.
- 구슬 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
풀이
노드의 개수가 별로 많지 않습니다.
일일히 모든 노드를 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 |