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

🔗 문제 링크

BOJ 15591번: MooTube (Silver)

15591번: MooTube (Silver)

 

📝 풀이 과정

문제를 보면 N까지의 영상이 존재하는데 영상끼리 가는 경로는 무조건 존재하며, 개수는 N - 1개라고 주어진다. 이것으로 주어진 그래프가 Spanning Tree(신장 트리, 최소 연결 부분 그래프)임을 알 수 있다.

 

 

따라서, 만약 A → B로가는 연결이 끊어진다면 A → B로는 갈 수 없게 되며 A에서 출발해 B에서 연결된 다른 간선들도 도달할 수 없게 된다는 것을 의미하게 된다. 이를 활용해 BFS를 돌며 영상 사이의 거리가 K보다 작게 되면 해당 영상에서 갈 수 있는 모든 USADO의 크기가 K이하가 되기 때문에 탐색을 하지 않도록 BFS를 돌지 않도록 Queue에 추가하지 않으면 된다.

 

추가적으로, 간선의 개수가 노드의 개수에 비해 매우 작기 때문에 2차 배열이 아닌 ArrayList[]형태로 저장하는 것이 시간의 효율성을 증가시킨다.

 

⏱ 시간 복잡도

BFS를 Q번 반복하기 된다. 인접리스트 BFS의 시간복잡도는 $O(V + E)$.

따라서 시간복잡도는 $O(Q\times(V + E))$가 된다.

 

V와 E는 각각 최대 5000과 4999가 되지만 5000으로 생각해주었고, Q는 최대 5000이다.
$ (5000 + 5000) \times 5000 = 10^4\times5\times10^3 = 5\times10^7 < 10^8$

 

💻 코드

import java.util.*;

public class Main {
    static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(), Q = sc.nextInt();

        List<int[]>[] adj = new ArrayList[N + 1];

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

        for (int i = 1; i < N; i++) {
            int p = sc.nextInt(), q = sc.nextInt(), r = sc.nextInt();
            adj[p].add(new int[]{q, r});
            adj[q].add(new int[]{p, r});
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < Q; i++) {
            int k = sc.nextInt(), v = sc.nextInt();

            boolean[] visit = new boolean[N + 1];
            visit[v] = true;
            Queue<Integer> que = new LinkedList<>();
            que.add(v);

            int ans = 0;
            while (!que.isEmpty()) {
                int cur = que.poll();

                for (int[] a : adj[cur]) {
                    if (!visit[a[0]] && a[1] >= k) {
                        que.add(a[0]);
                        visit[a[0]] = true;
                        ans++;
                    }
                }
            }
            sb.append(ans).append('\n');
        }
        System.out.println(sb.toString());
    }
}

 

📊 제출 결과