MooTube - 15591[G5]

문제

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

 

풀이

주요 목표는 특정 동영상에서 시작하여, 주어진 'USADO' 값 이상인 모든 동영상을 찾는 것이다.

'USADO'는 동영상 간의 연결 강도를 나타내는 값이며, Q에서 K와 시작 노드의 번호를 불러줄 때, 그 값 이상의 노드들의 개수를 판별한다.

 

1. DFS(깊이 우선 탐색) 사용

각 질문에 대해 DFS를 수행하여, 모든 연결된 노드들을 탐색한다.

 

2. 경로상의 최소 USADO 값 유지

탐색 과정에서 USADO가 기준 이상인 경로를 따라 노드들을 방문하고, minUSADO 파라미터를 통해 경로 간 최소 값을 재귀에 사용하였다.

 

코드

 

import java.io.*;
import java.util.*;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    static int N, Q, count;
    static List<ArrayList<int[]>> MooTube; //그래프
    static boolean[] visited;
    
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());
        MooTube = new ArrayList<ArrayList<int[]>>();
        //초기화
        for(int i = 0; i < N; i++) {
            MooTube.add(new ArrayList<int[]>());
        }
        
        //값 넣기
        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 dist = Integer.parseInt(st.nextToken());     
            //1. 시작점 넣기
            MooTube.get(start - 1).add(new int[] {end - 1, dist});
            
            //2. 끝점 넣기
            MooTube.get(end - 1).add(new int[] {start - 1, dist});
        }
        
        //판별
        for(int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());
            int dist = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken()) - 1;
            
            count = 0;
            visited = new boolean[N]; //방문 여부
            dfs(start, dist, Integer.MAX_VALUE); //DFS 시행
            
            bw.write(count + "\n");
        }
        
        bw.flush();
        bw.close();
    }
    
    static void dfs(int node, int dist, int minUSADO) {
        visited[node] = true; //방문 처리

        for(int[] edge : MooTube.get(node)) {
            int nextNode = edge[0];
            int nextDist = edge[1];
            
            if(!visited[nextNode]) {
                int newMinUSADO = Math.min(minUSADO, nextDist); //지금까지 경로의 최저 USADO값
                if(newMinUSADO >= dist) { //그 값이 목표 dist보다 높다면 다시 재귀 시행
                    count++;
                    dfs(nextNode, dist, newMinUSADO);
                }
            }
        }
    }
}