[백준] 15591: MooTube (Silver) - JAVA

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

 

풀이

N번까지 번호를 가진 동영상들이 서로 연결되어있다.

 

연결마다 유사도가 k의 값으로 정해져 있다. 경로를 연결하여 유사도들 중 최소값이 두 동영상의 유사도가 된다.

 

특정 값을 정해 유사도가 그 값 이상인 동영상들의 개수를 묻는 문제이다.

 

시작 정점으로 할 동영상의 번호와, 특정 값이 주어지면 bfs탐색을 진행했다.

 

연결된 노드들을 탐색하여 유사도가 특정 값 K 이상일 때 카운트를 1증가시키며 큐에 넣어 계속했다.

 

---

 

메모리: 80360KB
시간: 1008ms
언어: Java 11

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

public class Main {
    static class Node {
        int v;
        int cost;

        public Node(int v, int cost) {
            this.v = v;
            this.cost = cost;
        }
    }

    static int n;
    static ArrayList<ArrayList<Node>> list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

        list = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            list.get(a).add(new Node(b, c));
            list.get(b).add(new Node(a, c));
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(connect(a, b)).append("\n");
        }

        System.out.println(sb);
    }

    private static int connect(int k, int v) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visit = new boolean[n + 1];
        queue.add(v);
        visit[v] = true;

        int answer = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();

            for (Node next : list.get(node)) {
                if (visit[next.v]) {
                    continue;
                }

                if (next.cost >= k) {
                    answer++;
                    queue.add(next.v);
                    visit[next.v] = true;
                }
            }
        }

        return answer;
    }

}