개발 블로그

문제

농부 존은 남는 시간에 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번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 USADO는 min(3,2)=2가 되고, 1번 동영상과 4번 동영상의 USADO는 min(3,4)=3이 되고, 3번 동영상과 4번 동영상의 USADO는 min(2,4)=2가 된다.

농부 존은 K=1일 때 2번 동영상, K=3일 때 1번 동영상, K=4일 때 1번 동영상을 보면 각각 몇 개의 동영상이 추천될까 궁금해하고 있다. K=1일 때 2번 동영상에서 추천되는 동영상은 1, 3, 4번 동영상이다. K=4일 때 1번 동영상으로부터 추천되는 동영상은 없다. 그러나 K=3일때는 1번 동영상에서 2번 동영상과 4번 동영상이 추천된다.

접근 방법

처음에는 노드간 모든 pair에 대해, a->b 노드로 가는 edge의 min을 구해서 a, b 노드 간의 usado를 처음부터 다 구해놓으려고 했었다. 

이 방법은 너무 비효율적일 것 같아서 각 Question마다 주어지는 k와 v에 대해서만 확인해서 그때그때 답을 구하는 것이 좋을것 같았다. 

그러기 위해 각각 연결된 노드들의 정보들만 저장하는 리스트 graphList를 생성했다. 

graphList[1]에는 1번 노드와 연결된 모든 노드와, 그 노드까지의 edge 정보를 저장해놓는다. (그 정보는 Node 객체에 넣어서 저장한다)

위 예제로 예시를 들면 graphList에 담긴 정보는 아래와 같다. 

graphList[1] => (2,3)

graphList[2] => (1,3), (3,2), (4,4)

graphList[3] => (2, 2)

graphList[4] => (2, 4)

그래서 매 Question마다 bfs를 도는데, graphList[현재노드] 의 크기만큼 돌게 되며(시작 노드와 다이렉트로 연결된 노드 모두 방문해가면서), 다이렉트로 연결되지 않은 노드에 대해서도 que.add를 통해 탐색 대상에 넣어 탐색을 하게 된다. 

import java.util.*;
public class BOJ_15591_MoonTube {
    static class Node{
        int node, weight;
        public Node(int n, int w){
            this.node = n;
            this.weight = w;
        }
    }

    static int bfs(int k, int v, ArrayList<ArrayList<Node>> graphList, int N){
        int[] visited = new int[N+1]; //노드번호 1부터 ~ N까지이므로 N+1개
        int cntVideo = 0;
        Queue<Integer> que = new LinkedList<Integer>();
        que.add(v);   //시작 노드
        visited[v] = 1;

        while(!que.isEmpty()) { //방문할 노드가 없을 때까지
            int curNode = que.poll();

            for(int i = 0; i<graphList.get(curNode).size(); i++){
                int w = graphList.get(curNode).get(i).weight;   //usado
                int n = graphList.get(curNode).get(i).node;
                if(w<k || visited[n] != 0) {continue;}    //문제에서 weight가 k이상일 때만 (w>=k)물어봄, w<k인 케이스는 패스

                que.add(n);     //다음 방문할 노드 저장. v노드와 다이렉트로 연결되지 않은 노드에 대해서도 탐색 가능 
                visited[n] = 1;
                cntVideo++;

            }
        }
        return cntVideo;
    }

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int Q = sc.nextInt();
        ArrayList<ArrayList<Node>> graphList = new ArrayList<ArrayList<Node>>();    //graphList[x]에는 x 노드와 연결된 노드의 정보와 간선 정보가 객체로 들어있다.
        for(int i = 0; i<=N; i++){//노드 1~N까지 있으므로
            graphList.add(new ArrayList<Node>());
        }
        for(int i = 1; i<=N-1; i++){
            int p = sc.nextInt();
            int q = sc.nextInt();
            int r = sc.nextInt();
            //그래프 정보 입력. 간선에 연결된 노드 양쪽에 대해 각각 정보 입력
            graphList.get(p).add(new Node(q,r));
            graphList.get(q).add(new Node(p,r));
        }
        ArrayList<Integer> ansList = new ArrayList<Integer>();
        for(int i = 1; i<=Q; i++){
            int k = sc.nextInt();
            int v = sc.nextInt();
            int ans = bfs(k, v, graphList, N);
            ansList.add(ans);
        }
        for(int i = 0; i<ansList.size(); i++){
            System.out.println(ansList.get(i));
        }



    }
}

참고 : https://fjvbn2003.tistory.com/873