15591번 : MooTube (Silver) [C++]

문제 링크

성공 여부(걸린 시간): 성공(50분)

아이디어

간단하게 BFS로 풀 수 있는 문제였으나 C++ 문법이 기억이 안나서 동적할당하느라 30분 정도 소요한 것 같다.

❌ -> 처음에는 플로이드-워셜 알고리즘으로 풀어볼까 했으나
시간 복잡도가 N^3인 해당 알고리즘으로는 N이 최대 5000개인 이 문제를 풀기는 어렵다고 생각했고

⭕ -> BFS를 통해서 지나온 간선 중에 최소의 가중치인 USADO가 K이상인 영역까지만 노드의 수를 카운팅하여 출력하면
문제에서 원하는 값을 구할 수 있게 됨을 인지하고 그렇게 풀게 되었다.

풀이코드

#include<iostream>
#include<vector>
#include<algorithm>
#include <queue>
using namespace std;
static int INF_MAX = 210000000;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    vector<vector<pair<int, int>>> usado(N + 1);

    for (int i = 0; i < N-1; i++) {
        int p, q, r;
        cin >> p >> q >> r;
        usado[p].push_back({ q,r });
        usado[q].push_back({ p,r });
    }

    for (int i = 0; i < Q; i++) {
        int k, v;
        cin >> k >> v;
        //BFS를 통해서 이번에 몇개의 동영상을 추천할지 고르기
        queue<int> q;
        vector < bool> visited(N+1, false);
        visited[v] = true;
        int cnt = 0;
        for (pair<int, int> edge : usado[v]) {
            if (edge.second<k) {
                continue;
            }
            q.push(edge.first);
            visited[edge.first] = true;
        }
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            cnt++;
            for (pair<int, int> nextEdge: usado[cur]) {
                int next = nextEdge.first;
                if (!visited[next] && k<=nextEdge.second) {
                    visited[next] = true;
                    q.push({next});
                }
            }
        }
        cout << cnt << "\n";
    }
    return 0;
}

/*
USADO가 K 이상인 동영상은 
해당 지점까지 가는데에 간선의 최대값이 K보다 커야한다는 뜻

BFS로 가다가 K보다 큰 경우만 추가해주다가 K보다 작은 경우를 만나면 종료하고 
탐색을 진행했던 노드들의 수를 카운팅 해서 출력해주면 됨
*/