[BOJ][Java]Q15591 - MooTube

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

15591번: MooTube (Silver)

문제 풀이

처음엔 잘못 이해해서, 가중치 최단경로를 구하는 문제인 줄 알았다.

하지만 다시 보니 가중치의 합이 아니고 가장 작은 유사도를 갖게 하는 것이었다.

따라서 이 문제는 BFS, 너비우선그래프탐색 문제이다.

 

Edge 클래스를 생성하여, 정점과 유사도를 저장하였다.

ArrayList<Edge>[] 배열을 만들어 인접리스트로 그래프 정보를 저장하였다.

 

일반적인 bfs와 똑같이 탐색하되,

큐에 자식Edge를 넣을 때 Edge의 유사도를 Long.min(부모의 유사도, 자식의 유사도)로 저장하였다.

이렇게 하면 부모부터 타고 내려올 때, 가장 작은 값을 저장할 수 있다.

 

처음엔 min값을 변수에 따로 저장하는 방식을 생각했는데,
이렇게 하면 자식들을 검사하는 중 부모까지의 min값이 바뀐다.

바뀌지 않도록 예외처리해준다고 해도, 각각의 자식을 통해 이동한 다음 자식들 경로에 저장된 min값이 모두 다르므로

다른 방식을 통해 복잡하게 예외처리 해주지 않는 한 불가능하다.

따라서 그냥 큐에 담으면 되겠구나라고 지금의 방법을 생각해냈다.

 

전체 코드

package graph_traversal.bfs;

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

public class Q15591_MooTube {
    /*[골드5]Q15591 - MooTube*/
    static int n, q;
    static boolean[] visited;
    static ArrayList<Edge>[] network;

    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());

        network = new ArrayList[n+1];
        for(int i =0; i<n+1;i++){
            network[i] = new ArrayList<>();
        }
        visited = new boolean[n+1];

        for(int i = 0; i<n-1;i++){
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            network[v1].add(new Edge(v2,w));
            network[v2].add(new Edge(v1,w));
        }


        for(int i = 0; i<q; i++){
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            int video = Integer.parseInt(st.nextToken());

            Arrays.fill(visited,false);
            bfs(k, video);

        }

    }

    static void bfs(int k, int v){
        int cnt = 0;    //k 이상인 비디오 개수
        Queue<Edge> q = new ArrayDeque<>();
        q.offer(new Edge(v, Long.MAX_VALUE));
        while(!q.isEmpty()){
            Edge now = q.poll();
            visited[now.v] = true;
            if(now.usado >= k && now.usado!=Long.MAX_VALUE) cnt++;
            for(Edge e: network[now.v]){
                if(!visited[e.v]){
                    //부모와 자식 중 더 작은 유사도로 큐에 넣기
                    q.add(new Edge(e.v, Long.min(e.usado, now.usado)));
                }
            }
        }
        System.out.println(cnt);
    }
    static class Edge{
        int v;
        long usado;

        public Edge(int v, long usado) {
            this.v = v;
            this.usado = usado;
        }
    }
}