[BOJ 백준] 15591번 MooTube (Silver)

문제

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

15591번: MooTube (Silver)

접근

한 정점에서 다른 정점으로의 USADO값의 최솟값을 구하기 위해 모든 정점에서부터 BFS를 돌아준 뒤 입력받은 K값보다 크거나 같은 값을 USADO로 가지는 것을 세주어서 문제를 풀었다. 다만 다 풀고 나니 이 과정을 따로 나눌 필요 없이 BFS 한 번에 해결할 수 있도록 짰으면 메모리와 시간을 더 효율적으로 사용했을 수 있다는 것을 깨달았다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<pair<int, int>> moo[5005];
int mootube[5001][5001];

int counter(int k, int start) {
    int ans = 0;
    for (int i = 0; i < moo[start].size(); i++) {
        if (moo[start][i].second >= k)
            ans++;
    }
    return ans;
}

int main() {
    int n, q, a, b, c;
    cin >> n >> q;
    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b >> c;
        moo[a].push_back({b, c}); 
        moo[b].push_back({a, c});
    }
    for (int i = 0; i < 5001; i++) {
        if (moo[i].size() == 0)
            continue;
        queue<pair<int, int>> q;
        bool visit[5001] = {0};
        q.push({i, -1});
        while (!q.empty()) {
            pair<int, int> f = q.front();
            q.pop();
            visit[f.first] = 1;
            for(int j = 0; j < moo[f.first].size(); j++) {
                if (visit[moo[f.first][j].first] == 1)
                    continue;
                if (f.second == -1) {
                    visit[moo[f.first][j].first] = 1;
                    q.push({moo[f.first][j].first, moo[f.first][j].second});
                } else {
                    q.push({moo[f.first][j].first, min(f.second, moo[f.first][j].second)});
                    mootube[i][moo[f.first][j].first] = min(f.second, moo[f.first][j].second);
                    mootube[moo[f.first][j].first][i] = min(f.second, moo[f.first][j].second);
                }
            }
        }
    }
    for (int i = 0; i < 5001; i++) {
        for (int j = 0; j < 5001; j++) {
            if (mootube[i][j] != 0)
                moo[i].push_back({j, mootube[i][j]});
        }
    }
    for (int i = 0; i < q; i++) {
        cin >> a >> b;
        cout << counter(a, b) << "\n";
    }
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study