AlgorithmBOJ

백준 Mootube 15591

, ,

1. 백준 MOOTUBE 15591 문제

1.1. 문제

농부 존은 남는 시간에 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 값에 대한 추천 동영상의 개수를 묻는 질문 여러 개에 당신이 대답해주기를 바란다.

1.2. 입력

입력의 첫 번째 줄에는 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를 보고 있는 소들에게 몇 개의 동영상이 추천될 지 묻는 것이라는 것을 뜻한다.

1.3. 출력

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

1.4. 예제 입력 1

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

1.5. 예제 출력 1

3
0
2

1.6. 힌트

농부 존은 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번 동영상이 추천된다.

1.1. 컴퓨팅적 사고

문제를 살펴보면 K값은 유사도를 뜻하고 K값이상으로 연결된 노드만 동영상을 추천시킬 수 있습니다. 인접된 노드들과의 관계에서 정답을 구해야하므로 인접리스트로 풀어야겠다는 생각을 하게 되었습니다.

가장 먼저 인접리스트를 생성시켜서 모든 값들을 넣어주고 (유사도, 출발시작 노드)의 값을 바탕으로 BFS를 진행해줍니다. 모든 경우에 대해서 매번 다르게 수행해야하므로 check를 모두 초기화시키면서 진행합니다. 즉, 해당노드에서 시작되는 노드와 연결된 값을 모두 찾아줍니다. 그리고 유사도값 이상인 가중치값을 가진 값들을 찾아주면 됩니다.

노드에 대한 체크는 check변수로 해당 노드를 방문했는지를 체크해주고 해당 인접리스트에 가지고 있는 value의 값이 k이상일때만 다음 노드를 방문할 수 있게 해줍니다. 해당 조건을 만족한다면 answer의 값을 카운팅 시켜주면 동영상 추천이 가능한 노드의 개수를 구할 수 있게 됩니다. 결론적으로 인접리스트와 BFS를 활용한 문제였으며 문제가 길고 복잡해보였지만 생각을 조금만 달리한다면 쉽게 풀 수 있던 문제였습니다.

1.2. 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public class baekjoon_Mootube15591_kgh {
    static int n;
    static int q;
    static boolean[] check;
    static int answer = 0;
    static List<List<Pair>> arr = new ArrayList<>();
    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());
        initListNode();
        for(int i=0; i<n-1; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            arr.get(x).add(new Pair(y,value));
            arr.get(y).add(new Pair(x,value));
        }

        for(int i=0; i<q; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int k = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            bfs(k, v);          // k이상의 유사도, 시작노드
            System.out.println(answer);
            answer=0;
        }
    }

    private static void initListNode() {
        IntStream.rangeClosed(0, n).forEach(i -> arr.add(new ArrayList<>()));
    }
    private static void bfs(int k, int v) {
        check = new boolean[5001];
        Queue<Integer> q = new LinkedList<>();
        check[v] = true;
        q.add(v);

        while(!q.isEmpty()) {
            int node = q.remove();
            // 연결된 노드에 있는것들을 모두 가져와서 체크
            for (int i = 0; i < arr.get(node).size(); i++) {
                int y = arr.get(node).get(i).y;
                int value = arr.get(node).get(i).value;
                // 방문하지 않은 노드이고, 가중치값이 k보다 크거나 같을 경우만 진행한다. 그 외의 경우에는 진행하지 않는다. 조건을 만족 X
                if (!check[y] && value >= k) {
                    q.add(y);
                    check[y] = true;
                    answer++;
                }
            }
        }
    }
    static class Pair{
        int y;
        int value;
        public Pair(int y, int value) {
            this.y = y;
            this.value = value;
        }
    }
}
Share