[BOJ] 백준 15591 MooTube (Silver) c++ (그래프 이론, bfs)

문제 출처 : https://www.acmicpc.net/problem/15591

15591번: MooTube (Silver)

---

풀이

문제가 길고 영어 번역본이라 거부감이 들 수 있겠으나.. 결론은 연결되어 있는 그래프를 탐색하는 대표적인 그래프 탐색 문제이다.

이런 그래프 문제는 보통 아래와 같은 방법으로 처리한다.

1. vector를 배열로 선언한다.
2. a b가 연결되어 있을 경우 서로 푸시한다. v[a].push_back(값), v[b].push_back(값)
3. 탐색하는 경우 bfs방식으로 탐색한다.

vector<pair<int, int>> v[5000+1]; // idx, val
for(int i = 0; i < N-1; i++){
    int a, b, c;
    cin >> a >> b >> c;
    v[a].push_back({b, c});
    v[b].push_back({a, c});
}

이후 bfs로 탐색하며 k값 이상인 경우 정답에 추가해주면 끝이다!

---

코드

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> v[5000+1]; // idx, val

int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int N, Q;
    cin >> N >> Q;

    for(int i = 0; i < N-1; i++){
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    for(int i = 0; i < Q; i++){
        vector<bool> visit(5000+1, false);
        int ans = 0;
        int k, video;
        cin >> k >> video;
        queue<int> q;
        visit[video] = true;
        q.push(video);
        while(!q.empty()){
            int now_idx = q.front();
            q.pop();
            for(int j = 0; j < v[now_idx].size(); j++){
                int next_idx = v[now_idx][j].first;
                if(visit[next_idx]) continue;
                int next_val = v[now_idx][j].second;
                if(next_val >= k){
                    visit[now_idx] = true;
                    ans++;
                    q.push(next_idx);
                }
            }
        }
        cout << ans << '\n';
    }
	return 0;
}