[BOJ] 15591 번 - MooTube(Silver)

15591번 - MooTude(Silver)

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512MB	673	326	258	56.828%

문제

농부 존은 남는 시간에 MooTube라 불리는 동영상 공유 서비스를 만들었다. MooTube에서 농부 존의 소들은 재밌는 동영상들을 서로 공유할 수 있다. 소들은 MooTube에 1부터 N까지 번호가 붙여진 N (1 ≤ N ≤ 5,000)개의 동영상을 이미 올려 놓았다. 하지만, 존은 아직 어떻게 하면 소들이 그들이 좋아할 만한 새 동영상을 찾을 수 있을지 괜찮은 방법을 떠올리지 못했다.

농부 존은 모든 MooTube 동영상에 대해 “연관 동영상” 리스트를 만들기로 했다. 이렇게 하면 소들은 지금 보고 있는 동영상과 연관성이 높은 동영상을 추천 받을 수 있을 것이다.

존은 두 동영상이 서로 얼마나 가까운 지를 측정하는 단위인 “USADO”를 만들었다. 존은 N-1개의 동영상 쌍을 골라서 직접 두 쌍의 USADO를 계산했다. 그 다음에 존은 이 동영상들을 네트워크 구조로 바꿔서, 각 동영상을 정점으로 나타내기로 했다. 또 존은 동영상들의 연결 구조를 서로 연결되어 있는 N-1개의 동영상 쌍으로 나타내었다. 좀 더 쉽게 말해서, 존은 N-1개의 동영상 쌍을 골라서 어떤 동영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재하도록 했다. 존은 임의의 두 쌍 사이의 동영상의 USADO를 그 경로의 모든 연결들의 USADO 중 최솟값으로 하기로 했다.

존은 어떤 주어진 MooTube 동영상에 대해, 값 K를 정해서 그 동영상과 USADO가 K 이상인 모든 동영상이 추천되도록 할 것이다. 하지만 존은 너무 많은 동영상이 추천되면 소들이 일하는 것이 방해될까 봐 걱정하고 있다! 그래서 그는 K를 적절한 값으로 결정하려고 한다. 농부 존은 어떤 K 값에 대한 추천 동영상의 개수를 묻는 질문 여러 개에 당신이 대답해주기를 바란다.

입력

입력의 첫 번째 줄에는 N과 Q가 주어진다. (1 ≤ Q ≤ 5,000)

다음 N-1개의 줄에는 농부 존이 직접 잰 두 동영상 쌍의 USADO가 한 줄에 하나씩 주어진다. 각 줄은 세 정수 pi, qi, ri (1 ≤ pi, qi ≤ N, 1 ≤ ri ≤ 1,000,000,000)를 포함하는데, 이는 동영상 pi와 qi가 USADO ri로 서로 연결되어 있음을 뜻한다.

다음 Q개의 줄에는 농부 존의 Q개의 질문이 주어진다. 각 줄은 두 정수 ki와 vi(1 ≤ ki≤ 1,000,000,000, 1 ≤ vi ≤ N)을 포함하는데, 이는 존의 i번째 질문이 만약 K = ki라면 동영상 vi를 보고 있는 소들에게 몇 개의 동영상이 추천될 지 묻는 것이라는 것을 뜻한다.

출력

Q개의 줄을 출력한다. i번째 줄에는 농부 존의 i번째 질문에 대한 답변이 출력되어야 한다.

---

예제 입력 1

4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 1

예제 출력 1

3

농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 USADO는 min(3,2)=2가 되고, 1번 동영상과 4번 동영상의 USADO는 min(3,4)=3이 되고, 3번 동영상과 4번 동영상의 USADO는 min(2,4)=2가 된다.

농부 존은 K=1일 때 2번 동영상, K=3일 때 1번 동영상, K=4일 때 1번 동영상을 보면 각각 몇 개의 동영상이 추천될까 궁금해하고 있다. K=1일 때 2번 동영상에서 추천되는 동영상은 1, 3, 4번 동영상이다. K=4일 때 1번 동영상으로부터 추천되는 동영상은 없다. 그러나 K=3일때는 1번 동영상에서 2번 동영상과 4번 동영상이 추천된다.

출처

www.acmicpc.net/problem/15591

15591번: MooTube (Silver)

알고리즘 분류

• 그래프 이론
• 그래프 탐색

접근 방법

모든 노드들이 연결되어진 완전 그래프 형태의 노드이므로, USADO의 값은 모두 INF가 아닌 것이 보장된다.

현재 노드까지 오기 위해서 거쳐간 간선들의 가중치 중 최솟값을 유지하는 식으로 그래프 탐색을 진행해주면 된다.

또한, 모든 노드들이 연결 된 상태 이고 주어지는 간선의 개수는 N-1개 이므로 인접행렬로 연결관계를 표현하는 것은 비효율적이라는 생각이 들어 인접리스트로 연결관계를 표현하였다.

 

그래프탐색을 위해 필자는 BFS 알고리즘을 이용했다.

BFS를 각 노드마다 수행하면서, 모든 간선들을 경유하기 때문에 USADO의 최소값이 보장된다고 할 수 있다.

 

소스 코드

#define INF 1e12
#define ll long long
#include <bits/stdc++.h>
using namespace std;

int N,Q;
vector<pair<ll, int>> adj[5001];
vector<vector<ll>> USADO;

void BFS(int start){
    vector<bool> visited(N+1, false);
    // 큐에는 현재까지 경로로 오면서 가지는 USADO 의 최솟값과 해당 노드의 번호를 넣는다.
    queue<pair<ll,int>> q;
    visited[start] = true;
    USADO[start][start] = INF;

    q.push({INF, start});
    while(!q.empty()){
        auto front = q.front(); q.pop();
        int current = front.second;
        ll min_cost = front.first;

        for(int i=0; i<adj[current].size(); i++){
            int next = adj[current][i].second;
            ll cost = adj[current][i].first;

            if( visited[next] ) continue;
            visited[next] = true;
            if( min_cost > cost ){
                USADO[start][next] = cost;
                q.push({cost, next});
            }
            else{
                USADO[start][next] = min_cost;
                q.push({min_cost, next});
            }

        }

    }

}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> N >> Q;
    USADO.resize(N+1, vector<ll>(N+1, INF));

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

    // BFS를 통해 그 경로의 모든 연결들의 USADO중 최솟값을 정한다.
    for(int i=1; i<=N; i++){
        BFS(i);
    }


    // output
    for(int i=0; i<Q; i++){
        ll k, v;
        cin >> k >> v;
        int cnt = 0;
        for(auto item : USADO[v]){
            if( item >= k && item < INF )
                cnt += 1;
        }
        cout << cnt << '\n';
    }


    return 0;
}