BOJ 15591 - MooTube (Silver)

문제

농부 존은 MooTube라는 동영상 공유 서비스를 만들었다. 각 MooTube 동영상은 하나 이상의 다른 동영상과 연결되어 있으며, 두 동영상 사이의 연결에는 USADO(Udder Similarity Association Determination Organization)라는 기관이 매긴 유사도 점수(USADO)가 붙어 있다.

농부 존은 N개의 동영상을 트리 구조로 연결하려고 한다(N-1개의 간선으로 모든 노드가 연결된 트리). 두 동영상 사이의 연결 강도는 경로 상에 있는 간선 USADO 값들 중 최솟값으로 정의된다.

쿼리마다 시작 동영상 v와 기준값 k가 주어질 때, v에서 시작하여 연결 강도가 k 이상인 동영상의 수를 구하라.

입력

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

이후 N-1줄에 걸쳐 두 동영상 번호 p, q와 USADO 값 r이 주어진다.

이후 Q줄에 걸쳐 쿼리 k와 시작 동영상 v가 주어진다.

출력

각 쿼리마다 연결 강도가 k 이상인 동영상의 수를 출력한다.

예제

출력:

3
2
1

풀이

핵심 아이디어: N과 Q가 최대 5,000으로 작기 때문에 쿼리마다 BFS/DFS를 수행해도 O(Q × (N+E)) = O(N²) 안에 해결된다. 트리 위의 두 노드 사이 연결 강도는 경로 상 간선의 최솟값이므로, BFS 탐색 시 현재까지의 최솟값이 k 이상인 경우에만 이웃 노드를 큐에 추가하면 된다.

트리를 인접 리스트로 저장한다. 각 간선은 {노드, USADO값} 형태로 저장한다.
각 쿼리 (k, v)에 대해 BFS를 수행한다.
시작 노드 v를 큐에 넣고, 방문하지 않은 이웃 노드 중 간선 가중치가 k 이상인 경우에만 큐에 추가하고 카운트를 증가시킨다.
경로 전체의 최솟값이 k 이상이어야 하지만, 트리이므로 경로가 유일하고 BFS가 k 이상인 간선만 통과하므로 자동으로 보장된다.

코드

package day349;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Day311BOJ15591MooTube {
    static int N, Q;
    static List<int[]>[] edges;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());
 
        // 1부터 시작 0번 미사용
        edges = new ArrayList[N + 1];
 
        for (int i = 1; i < N + 1; i++) {
            edges[i] = new ArrayList<>();
        }
 
        // N - 1개 줄 입력
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int q = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            edges[p].add(new int[] { q, r });
            edges[q].add(new int[] { p, r });
        }
 
        for (int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            sb.append(bfs(k, v));
        }
 
        System.out.println(sb);
        br.close();
    }
 
    static boolean[] visited;
    static Queue<Integer> q;
 
    private static String bfs(int k, int v) {
        // 초기화
        int ans = 0;
        visited = new boolean[N + 1];
        q = new LinkedList<>();
 
        visited[v] = true;
        q.add(v);
 
        while (!q.isEmpty()) {
            int c = q.poll(); // 현재
            for (int[] edge : edges[c]) {
                int n = edge[0]; // 노드
                int r = edge[1]; // 비용
                if (!visited[n] && r >= k) {
                    visited[n] = true;
                    q.add(n);
                    ans++;
                }
            }
        }
        return ans + "\n";
    }
}

복잡도

시간: O(Q × (N + E)) = O(N²) — 각 쿼리마다 BFS 수행, N과 Q가 최대 5,000
공간: O(N + E) — 인접 리스트와 방문 배열

문제