백준 JAVA11 15591번 : MooTube (Silver)

Graph & BFS

문제 상세보기

Flow.

• 그래프 & BFS를 사용해서 풀이
• 가중치를 가진 양방향 그래프이다. (엣지 리스트)
• 간선수가 N-1이기 때문에 그래프 인접리스트로 구현

Point.

• 존은 임의의 두 쌍 사이의 동영상의 USADO를 그 경로의 모든 연결들의 USADO 중 최솟값으로 하기로 했다.

if(!visited[e.node] && e.usado >= k) 

• 조건문에서 USADO가 k이상인 엣지만 큐에 넣는다.
• 큐에 안들어간다는 의미는 주어진 k라는 값보다 작을 경우 뒤에 이어진 간선 역시 k이하의 수가 되기 때문에 해당 엣지 이후의 엣지는 더 이상 살펴보지 않는다는 의미

Code.

import java.util.*;

public class P15591_MooTube {
    static ArrayList<Edge>[] graph;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int Q = scanner.nextInt();

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

        for (int i = 1; i < N; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            int usado = scanner.nextInt();
            graph[start].add(new Edge(end, usado));
            graph[end].add(new Edge(start, usado));
        }

        for (int i = 0; i < Q; i++) {
            int k = scanner.nextInt();
            int v = scanner.nextInt();

            Queue<Edge> queue = new LinkedList<>();
            queue.add(new Edge(v, 0));
            visited = new boolean[N + 1];
            visited[v] = true;

            int count = 0;
            while (!queue.isEmpty()) {
                Edge current = queue.poll();
                int currentNode = current.node;
                for(Edge e : graph[currentNode]) {
                    if(!visited[e.node] && e.usado >= k) {
                        queue.add(e);
                        visited[e.node] = true;
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }
}

class Edge {
    int node;
    int usado;

    public Edge(int node, int usado) {
        this.node = node;
        this.usado = usado;
    }
}