반응형
https://www.acmicpc.net/problem/19538
19538번: 루머
예제 1 0분 : 최초 유포자($1$, $6$번 사람)가 루머를 생성한다. 1분 : $1$번 사람은 $2$, $3$번 사람에게 루머를 퍼뜨린다. $2$번 사람은 주변인 $2$명 중 $1$명이 루머를 믿고 있어 루머를 믿게 된다. $3$
www.acmicpc.net
[ 문제풀이 ]
1. vector list를 만들어 그래프를 저장합니다.
2. visited 배열과 cnt 배열을 만들어 i번 사람이 루머를 믿는지와 i번 사람의 주변에 루머를 믿는 사람의 수를 각각 저장합니다.
3. bfs를 통해 i번 사람이 루머를 믿게 될 때 주변 사람들의 cnt 배열 값을 1씩 늘려줍니다.
4. list[ next ].size() / 2 보다 cnt [ next ]의 값이 크거나 같으면 queue에 넣고 ans [ next ]에 현재 시간에 1을 더한 값을 저장하고, 방문 처리를 해줍니다.
5. for문으로 모든 노드를 돌면서 ans 값을 출력합니다.
[ 소스코드 ]
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 51 52 53 54 55 56 57 58 59 60 61 | #include<iostream> #include<vector> #include<queue> #include<cstring> using namespace std; int N, M; vector<int> list[200001]; int visited[200001]; int ans[200001]; int cnt[200001]; int main() { queue<pair<int,int>> q; scanf("%d", &N); memset(ans, -1, 4 * (N + 1)); int n; for (int i = 1; i <= N; i++) { while (1) { scanf("%d", &n); if (n == 0) break; list[i].push_back(n); } } scanf("%d", &M); for (int i = 0; i < M; i++) { scanf("%d", &n); q.push({ n, 0 }); ans[n] = 0; visited[n] = 1; } while (!q.empty()) { const int cur = q.front().first; const int min = q.front().second; q.pop(); for (auto next : list[cur]) { if (visited[next] != 1) { cnt[next]++; if (cnt[next] >= (float)list[next].size() / 2.0f) { visited[next] = 1; ans[next] = min + 1; q.push({ next, min + 1 }); } } } } for (int i = 1; i <= N; i++) { printf("%d ", ans[i]); } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 23793번 - 두 단계 최단 경로 1 (C++) (0) | 2022.12.26 |
|---|---|
| [ 백준 ] 1759번 - 암호 만들기 (C++) (0) | 2022.12.25 |
| [ 백준 ] 1922번 - 네트워크 연결 (C++) (0) | 2022.12.23 |
| [ 백준 ] 14395번 - 4연산 (C++) (0) | 2022.12.22 |
| [ 백준 ] 12738번 - 가장 긴 증가하는 부분 수열 3 (C++) (0) | 2022.12.21 |