[BOJ] 백준 15591 MooTube(Silver) (JAVA)

참고)

https://www.acmicpc.net/problem/15591 

15591번: MooTube (Silver)

 

 

풀이

해당 문제에서는 Q만큼의 두 정수 k와 v를 입력으로 주는데, 이 두 정수 관계를 이해하는데 시간이 오래 걸렸습니다. 

테스트 케이스를 손으로 그려보면서 따라가니 주어진 k, v가 의미하는 것은 ' v에서 시작해서 간선 비용이 k보다 크면 진출한다 '라는 결론을 내렸습니다.

어떤 동영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재해야하므로 MST 크루스칼방법을 생각했으나,

가중치의 합이 아닌 조건에 따라 경로를 따라가야하므로 Vedio 리스트 배열로 변경하여 bfs를 사용하여 해결했습니다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, Q;
    static List<Video>[] list;
    static int[][] question;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());
        list = new ArrayList[N + 1];

        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }

        question = new int[Q][2];  //k, v를 저장할 question 배열


        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            list[a].add(new Video(b, d));
            list[b].add(new Video(a, d)); //양방향 연결
        }

        for (int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken()); //유사도 K
            int v = Integer.parseInt(st.nextToken()); //시작점 V

            question[i][0] = k;
            question[i][1] = v;
        }

        for (int i = 0; i < Q; i++) {
            sb.append(bfs(question[i][0], question[i][1])).append("\n");
        }

        System.out.println(sb);

    }

    private static int bfs(int k, int v) {
        Queue<Video> queue = new LinkedList<>();
        boolean[] visited = new boolean[N+1];
        int min;
        int count = 0;

        queue.add(new Video(v, Integer.MAX_VALUE));

        while(!queue.isEmpty()){
            Video cur = queue.poll();  //현재 비디오
            visited[cur.to] = true;    //방문처리
            for(Video next : list[cur.to]){ //현재 비디오의 모든 경로
                if(!visited[next.to]){
                    min = Math.min(cur.distance,next.distance); //둘 연관도 중 최솟값
                    if(min>=k){  //그 최솟값이 k보다 크면 이동
                        queue.add(new Video(next.to, min));
                        count++;
                        visited[next.to] = true;
                    }
                }
            }
        }

        return count;
    }

    private static class Video {
        int to;
        int distance;

        public Video(int to, int distance) {
            this.to = to;
            this.distance = distance;
        }
    }
}