[백준/JAVA] 15591번: MooTube (Silver)

문제 보러가기

15591번: MooTube (Silver)

[문제 풀이]

USADO을 통해 알 수 있는 것은 USADO를 지나는 경로의 가중치 중 가장 작은 값을 가지게 된다.

 

예제를 예시로 들자면

1	2	3
2	3	2
2	4	4

1번과 4번 정점은 USADO로 연결되어 있지 않다. 그렇기 때문에 USADO에서 주어진 1번에서 2번 정점으로 가고

2번 정점에서 4번 정점으로 가는 방식으로 1번과 4번 정점을 연결하는데, 이때 가중치는 USADO를 통해 가는 경로 중에 최소의 값을 가진 가중치를 1번과 4번으로 가는 비용으로 생각한다.

즉, 1번에서 2번으로 가는 가중치 [3]과 2번에서 3번으로 가는 가중치 [2]중에서 1번에서 3번으로 가는 비용은

[3]과 [2] 중에서 작은 값인 2이다.

 

이때 문제의 힌트는 우리는 K값 이상을 가진 정점들 간의 비용의 개수를 구해야하는데, USADO를 통해 갈 때는 최소값을 가지고 가기 때문에 만약 한 정점에서 최소값이 K를 넘지 못한다면 그 정점을 제외해도 된다. 왜냐하면 그 정점은 어떻게

나중에 어떤 값을 가지던지 최소값을 가지고 가서 K를 넘지 못한다.

 

[코드]

import java.io.*; import java.util.*; class Main {     static int N, Q;     static List<List<int[]>> lists = new ArrayList<>();     public static void main(String[] args) throws IOException {         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());         for (int i = 0; i <= N; i++) lists.add(new ArrayList<>());         for (int i = 0; i < N - 1; i++) { //USADO 입력 주입             st = new StringTokenizer(br.readLine());             int A = Integer.parseInt(st.nextToken());             int B = Integer.parseInt(st.nextToken());             int value = Integer.parseInt(st.nextToken());             lists.get(A).add(new int[]{B, value});             lists.get(B).add(new int[]{A, value});         }         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(V, K)).append("\n");         }         System.out.println(sb);     }     public static int BFS(int V, int K) {         PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));         boolean[] visited = new boolean[N + 1];         int answer = 0;         visited[V] = true;          queue.add(new int[]{V, 0}); // 시작 정점은 체크하지 않는다.         while (!queue.isEmpty()) {             int[] temp = queue.poll();             List<int[]> list = lists.get(temp[0]);             for (int[] A : list) {                 if (visited[A[0]]) continue;                 if (A[1] >= K) { //최소값이 K를 넘길때만 큐에 넣는다.                     answer++;                     visited[A[0]] = true;                     queue.add(A);                 }             }         }         return answer;     } }