BOJ 15591 - MooTube (Silver)

15591번: MooTube (Silver)

 

1 ~ N까지의 동영상 존재(1≤N≤5,000)

연관 동영상 리스트를 만들기로 했다.

연관성 측정 = “USADO”

N-1개의 동영상 쌍을 골라서 어떤 동영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재.

임의의 두 쌍 사이의 동영상의 USADO = 그 경로의 모든 연결들의 USADO 중 최솟값

주어진 동영상에 대해 USADO가 K이상인 모든 동영상이 추천되도록 하려고 한다. 이때의 적절한 K값을 결정하려 한다.

USADO가 k일 때 i번 영상을 보고 있는 소들에게 몇 개의 동영상이 추천될지 출력하다.

우선 주어진 입력값 중 USADO인 r의 범위가 1≤r≤1,000,000,000이다. 10억으로 매우 크다.

동영상이 노드이며 양방향 가중치가 있는 그래프이다.

예제 입력을 보자.

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

일 때 1번과 2번은 USADO 3, 2번과 3번은 USADO 2, 2번과 4번은 USADO 4를 가지고 있다.

여기서 1번과 3번의 USADO를 계산해 보면 min(2, 3) = 2가 된다.

해당 경로에 있는 USADO 중 최소 값이다.

여기서 질문 4 1 이면 1번 기준 모든 USADO가 필요하다.

(1,2) = 3, (1,3) = 2, (1,4) = 3이며 k가 4이기 때문에 4 이상인 USADO가 없으므로 0개가 추천이 된다.

시작점부터 시작해 도달할 수 있는 모든 노드 사이에 비용이 k 이상인 것들의 개수를 세면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static class Edge {
        int to;
        int distance;

        Edge(int to, int distance) {
            this.to = to;
            this.distance = distance;
        }
    }

    static FastReader scan = new FastReader();
    static final int INF = Integer.MAX_VALUE;
    static int N, Q;
    static ArrayList<Edge>[] graph;
    static int[][] questions;

    static void input() {
        N = scan.nextInt();
        Q = scan.nextInt();
        graph = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            graph[i] = new ArrayList();
        }
        for (int i = 0; i < N - 1; i++) {
            int p = scan.nextInt() - 1;
            int q = scan.nextInt() - 1;
            int w = scan.nextInt();
            graph[p].add(new Edge(q, w));
            graph[q].add(new Edge(p, w));
        }

        questions = new int[Q][];

        for (int i = 0; i < Q; i++) {
            questions[i] = new int[]{scan.nextInt(), scan.nextInt() - 1}; //k, v
        }
    }

    static int bfs(int start, int k) {
        boolean[] visited = new boolean[N];
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visited[start] = true;
        int count = 0;

        while (!q.isEmpty()) {
            int curr = q.poll();

            for (Edge edge : graph[curr]) {
                if (!visited[edge.to]) {
                    int minUsado = Math.min(edge.distance, k);
                    if (minUsado >= k) {
                        visited[edge.to] = true;
                        q.add(edge.to);
                        count++;
                    }
                }
            }
        }
        return count;
    }

    static void solve() {
        for (int[] q : questions) {
            int k = q[0];
            int v = q[1];
            System.out.println(bfs(v, k));
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}