반응형
https://www.acmicpc.net/problem/15591
15591번: MooTube (Silver)
농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의
www.acmicpc.net
[ 문제풀이 ]
1. 각각의 노드 간 관계를 입력받을 때 쌍방향 그래프로 저장합니다.
2. k와 v를 입력 받으면 bfs를 통해 유사도가 k 이상인 값들을 queue에 넣고, k보다 작다면 queue에 넣지 않습니다.
3. 유사도가 k 이상이라면 ret++를 해주고 bfs가 끝날 때 ret를 return 해줍니다.
4. return 된 값을 출력해줍니다.
[ 소스코드 ]
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 62 63 64 | #include<iostream> #include<queue> #include<vector> #include<cstring> using namespace std; int N, Q; vector<pair<int,int>> list[5001]; int visited[5001]; int bfs(int k, int v) { queue<pair<int, int>> q; q.push({ v,987654321 }); memset(visited, 0, 4*(N+1)); int ret = 0; visited[v] = 1; while (!q.empty()) { const int cur = q.front().first; const int usado = q.front().second; q.pop(); for (auto next : list[cur]) { const int temp = min(usado, next.second); if (visited[next.first] != 1) { visited[next.first] = 1; if (temp >= k) { ret++; } else{ //유사도가 k보다 작은 값이 하나라도 있다면 이후 모두 낮기 때문에 continue; } q.push({ next.first, temp }); } } } return ret; } int main() { scanf("%d %d", &N, &Q); for (int i = 0; i < N-1; i++) { int p, q, r; scanf("%d %d %d", &p, &q, &r); list[p].emplace_back(q, r); list[q].emplace_back(p, r); } for (int i = 0; i < Q; i++) { int k, v; scanf("%d %d", &k, &v); printf("%d\n", bfs(k, v)); } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 2550번 - 전구 (C++) (0) | 2022.11.28 |
|---|---|
| [ 백준 ] 17182번 - 우주 탐사선 (C++) (0) | 2022.11.27 |
| [ 백준 ] 4991번 - 로봇 청소기 (C++) (0) | 2022.11.25 |
| [ 백준 ] 6087번 - 레이저 통신 (C++) (0) | 2022.11.24 |
| [ 백준 ] 4485번 - 녹색 옷 입은 애가 젤다지? (C++) (0) | 2022.11.23 |