[Java] 백준 15591번 - MoonTube

문제 링크 : https://www.acmicpc.net/problem/15591

15591번: MooTube (Silver)

 

문제

농부 존은 남는 시간에 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

힌트

농부 존은 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