백준 15591번 MooTube(자바) - bfs

문제

농부 존은 남는 시간에 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가 한 줄에 하나씩 주어진다. 각 줄은 세 정수 pi, qi, ri (1 ≤ pi, qi ≤ N, 1 ≤ ri ≤ 1,000,000,000)를 포함하는데, 이는 동영상 pi와 qi가 USADO ri로 서로 연결되어 있음을 뜻한다.

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

출력

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

예제 입력 1 복사

4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 1

예제 출력 1 복사

3
0
2

---

처음에는 다익스트라 알고리즘을 활용해 각 노드까지 가는 최소 거리를 구하는 방식으로 풀면 되는 줄 알았다.

하지만 문제에서

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

라는 부분이 있어서 예를 들어 

1과 3이 USADO 2으로 연결되어 있고, 3과 4가 USADO 3로 연결되어 있다면 1과 4의 USADO는 3과 2 중 작은 값인 2를 갖게 된다.

 

또한 존은 N-1개의 동영상 쌍을 골라서 어떤 동영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재하도록 했다 라고 했으므로 이는 각 노드들이 Spanning tree의 형태로 연결되어 있음을 알 수 있다.

 

따라서 만약 A → B로 가는 연결이 끊어진다면 A → B로는 갈 수 없게 되며 A에서 출발해 B에서 연결된 다른 간선들도 도달할 수 없다.
그렇기 때문에 BFS를 돌며 영상 사이의 거리가 K보다 작게 되면

(예를 들어 k가 3인데 1-3이 usado 2로 연결되어 있고, 3-4가 usado 3으로 연결되어 있다면 1-4의 usado는 2이므로 1 동영상 시청 시 3과 4 모두를 추천하지 않는다)

해당 영상에서 갈 수 있는 모든 USADO의 크기가 K이하가 되기 때문에 탐색을 하지 않도록 BFS를 돌지 않도록 Queue에 추가하지 않으면 된다.

import java.util.*;

class Node implements Comparable<Node>{
    int dest;
    int cost;
    Node (int dest, int cost) {
        this.dest = dest;
        this.cost = cost;
    }

    public int compareTo(Node o1) {
        if (this.cost < o1.cost)
            return -1;
        return 1;
    }
}
public class Main {
    static int n, q;
    static ArrayList<ArrayList<Node>> graph;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        q = sc.nextInt();
        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Node>());
        }
        for (int i = 0; i < n-1; i++) {
            int p = sc.nextInt();
            int q = sc.nextInt();
            int r = sc.nextInt();
            graph.get(p).add(new Node(q,r));
            graph.get(q).add(new Node(p,r));
        }
        for (int i = 0; i < q; i++) {
            int k = sc.nextInt();
            int v = sc.nextInt();
            System.out.println(bfs(v, k));
        }
    }

    public static int bfs(int start, int k) {
        Queue<Integer> que = new LinkedList<>();
        que.offer(start);
        boolean[] visited = new boolean[n+1];
        visited[start] = true;
        int cnt = 0;
        while (!que.isEmpty()) {
            int now = que.poll();
            for (int i = 0; i < graph.get(now).size(); i++) {
                int dest = graph.get(now).get(i).dest;
                int cost = graph.get(now).get(i).cost;
                if (visited[dest] || cost < k) {
                    continue;
                }
                visited[dest] = true;
                cnt++;
                que.offer(dest);
            }
        }
        return cnt;
    }
}

 

참고

[알고리즘 / 백준] 15591 - MooTube (Silver) (tistory.com)

[알고리즘 / 백준] 15591 - MooTube (Silver)

 

[백준/java] 15591 MooTube (velog.io)

[백준/java] 15591 MooTube