[백준] MooTube (Silver)

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

문제 요약

주어진 입력 K, V에 대해 V번 노드보다 K(가중치)이상으로 연결된 노드 개수 구하기

풀이 과정

처음 생각

인접 행렬을 이용해 특정 노드에서 다른 노드까지의 거리를 각각 구하는 것

생각 바꾸기

그런데 노드 개수 N개에 간선이 N-1개로 적기 때문에 굳이 인접 행렬로 하지 않아도 되고, 각 쿼리마다 어떤 노드에서 연결된 다른 노드들 중 조건 만족하는 곳만 찾으면 된다.
무엇보다 문제를 읽어보면 이는 트리라는 것을 알 수 있다.

핵심

어떤 노드에서 다른 노드로 갈 때 중간에 있는 여러 edges들 중 min(edges) >= K를 만족해야하지만 가능 경로에서 K보다 작다면 더 이상 볼 필요가 없다. 즉, 굳이 min(edges)를 구하지 않아도 된다.

흐름

• (u, v, cost)를 입력 받아 인접리스트에 add
• Q 개수 만큼 각 노드 u를 시작으로 dfs 순회해서 조건 K에 만족하는 경로가 있는지 찾기
• 있다면 cnt++

구현

import java.util.*;
import java.io.*;

public class Main {

    static class Pair {
        int end;
        int cost;

        public Pair(int end, int cost) {
            this.end = end;
            this.cost = cost;
        }
    }

    static int N, Q;
    static List<Pair>[] adj;
    static boolean[] isVisited;
    static int cnt;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());

        adj = new ArrayList[N+3];

        for(int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < N-1; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            adj[u].add(new Pair(v, cost));
            adj[v].add(new Pair(u, cost));
        }

        for (int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            int u = Integer.parseInt(st.nextToken());
            cnt = 0;
            isVisited = new boolean[N+3];

            dfs(u, k);
            sb.append(cnt).append('\n');
        }

        System.out.println(sb);
    }

    private static void dfs(int cur, int k) {

        isVisited[cur] = true;

        for (Pair nxt : adj[cur]) {
            if (!isVisited[nxt.end] && nxt.cost >= k) {
                cnt++;
                dfs(nxt.end, k);
            }
        }
    }
}