[백준 15591 C++][G5] MooTube(Silver)

⭐️ 난이도

 

Gold 5

---

⭐️ 문제

https://www.acmicpc.net/problem/15591

15591번: MooTube (Silver)

여태 다른 그래프 문제들과는 다르게 USADO라는 단어를 통해 문제를 설명해서, 얼핏 보면 어마무시해보이는 문제였다.

 

문제를 읽고 정리를 해보자.

1) 1~n까지 번호가 붙어있는 n개의 동영상이 있다.

2) 1~n개의 영상들 중에 n-1개의 가중치가 있는 간선이 있다.

3) USADO란 어떤 두 개의 영상에 있는 가중치들 중 제일 작은 가중치를 말한다.

4) 이 때, 정수 k와 v가 주어졌을 때, v에서 시작해서 USADO가 k 이상인 영상의 개수를 구하라.

 

---

⭐️ Idea flow

 

결국 영상(정점) v에서 시작해서 간선들의 가중치가 k 이상만 있는 정점의 개수를 구하면 된다.

여기서 주의할 점은

1) 가중치를 더해가면서 확인하는 것이 아니라, 가중치의 값을 단일로 확인

2) v와 바로 연결되어있지 않고 다른 정점을 통해서 도착하는 것 또한 okay

 

여기까지 생각이 진행됐다면 다음은 간단하다.

1) 정점 v에서 BFS 시작

2) for문과 저장한 간선 데이터를 이용하여 v와 연결된 모든 간선 검사 시작

3) 만일 간선의 가중치가 K보다 크거나 같다면 queue에 추가 및 result값 1 증가

4) BFS가 끝나면 result 값 출력

5) k와 v를 받아서 다시 BFS 시작

 

위와 같은 단계로 진행하면 된다.

 

---

⭐️ Code

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <unordered_set>
#include <unordered_map>

#define INF 987654321
#define MAX 1000000 + 1
using namespace std;

// 15591 - MooTube(Silver)
int n, q; // 영상의 개수, 질문의 개수
vector<vector<pair<int, long long>>> graph; // 간선 저장

void input(){
    cin >> n >> q;
    graph.assign(n + 1, vector<pair<int, long long>>(0, {0, 0}));

    for(int i = 0; i < n - 1; i++){
        int s, e;
        long long c;
        cin >> s >> e >> c;
        graph[s].emplace_back(make_pair(e, c));
        graph[e].emplace_back(make_pair(s, c));
    }
}

void BFS(long long k, int v){
    vector<int> isVisited(n + 1, false);
    isVisited[v] = true;

    queue<pair<int, long long>> q;
    q.push({v, k});
    int count = 0;

    while(!q.empty()){
        int cur = q.front().first;
        int cur_cost = q.front().second;
        q.pop();

        for(int i = 0; i < graph[cur].size(); i++){
            int next = graph[cur][i].first;
            int next_cost = graph[cur][i].second;

            if(!isVisited[next] && next_cost >= k){
                isVisited[next] = true;
                count++;
                q.push({next, next_cost});
            }
        }
    }

    cout << count << '\n';
    return;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    input();

    for(int i = 0; i < q; i++){
        long long k = 0;
        int v = 0;
        cin >> k >> v;
        BFS(k, v);
    }

    return 0;
}