[백준] 15591 - MooTube (Silver) (자바 Java)

[Gold V] MooTube (Silver) - 15591

문제 링크

성능 요약

메모리: 299080 KB, 시간: 1452 ms

분류

너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

농부 존은 남는 시간에 MooTube라 불리는 동영상 공유 서비스를 만들었다. MooTube에서 농부 존의 소들은 재밌는 동영상들을 서로 공유할 수 있다. 소들은 MooTube에 1부터 N까지 번호가 붙여진 N (1 ≤ N ≤ 5,000)개의 동영상을 이미 올려 놓았다. 하지만, 존은 아직 어떻게 하면 소들이 그들이 좋아할 만한 새 동영상을 찾을 수 있을지 괜찮은 방법을 떠올리지 못했다.

농부 존은 모든 MooTube 동영상에 대해 “연관 동영상” 리스트를 만들기로 했다. 이렇게 하면 소들은 지금 보고 있는 동영상과 연관성이 높은 동영상을 추천 받을 수 있을 것이다.

존은 두 동영상이 서로 얼마나 가까운 지를 측정하는 단위인 “USADO”를 만들었다. 존은 N-1개의 동영상 쌍을 골라서 직접 두 쌍의 USADO를 계산했다. 그 다음에 존은 이 동영상들을 네트워크 구조로 바꿔서, 각 동영상을 정점으로 나타내기로 했다. 또 존은 동영상들의 연결 구조를 서로 연결되어 있는 N-1개의 동영상 쌍으로 나타내었다. 좀 더 쉽게 말해서, 존은 N-1개의 동영상 쌍을 골라서 어떤 동영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재하도록 했다. 존은 임의의 두 쌍 사이의 동영상의 USADO를 그 경로의 모든 연결들의 USADO 중 최솟값으로 하기로 했다.

존은 어떤 주어진 MooTube 동영상에 대해, 값 K를 정해서 그 동영상과 USADO가 K 이상인 모든 동영상이 추천되도록 할 것이다. 하지만 존은 너무 많은 동영상이 추천되면 소들이 일하는 것이 방해될까 봐 걱정하고 있다! 그래서 그는 K를 적절한 값으로 결정하려고 한다. 농부 존은 어떤 K 값에 대한 추천 동영상의 개수를 묻는 질문 여러 개에 당신이 대답해주기를 바란다.

입력

입력의 첫 번째 줄에는 N과 Q가 주어진다. (1 ≤ Q ≤ 5,000)

다음 N-1개의 줄에는 농부 존이 직접 잰 두 동영상 쌍의 USADO가 한 줄에 하나씩 주어진다. 각 줄은 세 정수 p_i, q_i, r_i (1 ≤ p_i, q_i ≤ N, 1 ≤ r_i ≤ 1,000,000,000)를 포함하는데, 이는 동영상 p_i와 q_i가 USADO r_i로 서로 연결되어 있음을 뜻한다.

다음 Q개의 줄에는 농부 존의 Q개의 질문이 주어진다. 각 줄은 두 정수 k_i와 v_i(1 ≤ k_i ≤ 1,000,000,000, 1 ≤ v_i ≤ N)을 포함하는데, 이는 존의 i번째 질문이 만약 K = k_i라면 동영상 v_i를 보고 있는 소들에게 몇 개의 동영상이 추천될 지 묻는 것이라는 것을 뜻한다.

출력

Q개의 줄을 출력한다. i번째 줄에는 농부 존의 i번째 질문에 대한 답변이 출력되어야 한다.

 

---

풀이

처음에는 배열에 USADO를 모두 기록하고, USADO 배열을 돌면서 K 이상의 수를 찾으려고 하였다.

그런데 Q가 최대 5000, N이 최대 5000이므로 BFS의 시간 복잡도 O(V+E) * Q를 하면 O(10000) * 5000 < 10^8

이므로 각각의 Q마다 bfs를 실행하여도 괜찮았다.

 

그리고 각각의 USADO를 저장할 필요가 없이, Edge의 value가 K이상인 수만 queue에 추가하면 되었다.

최소 신장 트리를 활용한 문제다.

현재 edge의 val이 < K -> 더 고려할 필요 없음
val >=K -> 해당 edge와 연결된 다른 노드들의 값들과 비교해보기

K보다 작다면, edge에 연결된 다른 노드들도 최소값으로 업데이트가 되니까 더 이상 고려할 필요가 없다.

만약 K보다 크다면, queue에 추가해야 한다.

처음 V를 추가해서 queue에 추가하므로, V에 직접 연결된 노드들의 USADO는 해당 edge의 value가 된다.

그러므로 이 value가 K 이상이면 최소값으로 변경될 가능성이 없으므로 cnt를 더해준다.

 

이후 큐에 추가된 다른 노드들의 edge들은 value가 K 이상인 경우에만 queue에 추가되기 때문에 결국 USADO가 K이상인 노드들만 추가하게 된다.

 

처음에는 K 이상인 값들도 최소값으로 업데이트될 수 있기 때문에 다시 고려해야하지 않을까 싶었는데 최소 신장 트리의 특징을 생각해보면 간단히 풀 수 있는 문제였다.

 

package BOJ.Gold.g5;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_15591_MooTube {

    static class Edge {
        int start;
        int end;
        int value;

        public Edge(int start, int end, int value) {
            this.start = start;
            this.end = end;
            this.value = value;
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "start=" + start +
                    ", end=" + end +
                    ", value=" + value +
                    '}';
        }
    }


    static int N, Q;
    static List<Edge>[] adjList;


    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());
        Q = Integer.parseInt(st.nextToken());
        adjList = new List[N + 1];


        // bfs를 하면서 유사도 넣기

        for (int i = 1; i <= N; i++)
            adjList[i] = new ArrayList<>();
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            adjList[start].add(new Edge(start, end, value));
            adjList[end].add(new Edge(end, start, value));
        }


        StringBuilder sb = new StringBuilder();
        // 질문에 답하기
        for (int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());
            int K = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());
            int cnt = 0;
            // 최소 신장 트리

            /*
                현재 edge의 val이 < K -> 더 고려할 필요 없음
                val >=K -> 해당 edge와 연결된 다른 노드들의 값들과 비교해보기
             */
            boolean[] visit = new boolean[N + 1];
            visit[V] = true;
            Queue<Integer> q = new LinkedList<>();
            q.add(V);
            while (!q.isEmpty()) {
                int curr = q.poll();

                for (int j = 0; j < adjList[curr].size(); j++) {
                    Edge e = adjList[curr].get(j);
                    if (!visit[e.end] && e.value >= K) {
                        // K보다 큰 값을 찾는 것이니까, value가 K보다 작다면 해당 edge에 연결된 노드들은 무조건 K보다 작음, 더 볼 필요가 없다
                        // K보다 큰 노드만 추가하면 이후에 연결된 노드들을 추가할 때에도 K 이상인 애들만 계속 추가됨 -> 결국 K 이상인 노드만 cnt에 추가된다
                        q.add(e.end);
                        visit[e.end] = true;
                        cnt++;
                    }
                }
            }


            sb.append(cnt).append("\n");
        }
        System.out.print(sb);

    }
}