[백준/java] 15591 MooTube

15591 MooTube(Silver)
설명 출처 https://girawhale.tistory.com/53
스패닝 트리 https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

스패닝 트리

그래프 내의 모든 정점을 포함하는 트리

Spanning Tree = 신장 트리 = 스패닝 트리
Spanning Tree는 그래프의 최소 연결 부분 그래프 이다.
최소 연결 = 간선의 수가 가장 적다.
n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다.

즉, 그래프에서 일부 간선을 선택해서 만든 트리

문제 풀이

N까지의 영상이 존재하는데 영상끼리 가는 경로는 무조건 존재하며, 개수는 N - 1개라고 주어진다. 이것으로 주어진 그래프가 Spanning Tree(신장 트리, 최소 연결 부분 그래프) 임을 알 수 있다.

만약 A → B로 가는 연결이 끊어진다면 A → B로는 갈 수 없게 되며 A에서 출발해 B에서 연결된 다른 간선들도 도달할 수 없다.
이를 활용해 BFS를 돌며 영상 사이의 거리가 K보다 작게 되면 해당 영상에서 갈 수 있는 모든 USADO의 크기가 K이하가 되기 때문에 탐색을 하지 않도록 BFS를 돌지 않도록 Queue에 추가하지 않으면 된다.

시간 복잡도

• BFS를 Q번 반복하게 된다.
• 인접리스트 BFS의 시간복잡도는 O(V+E)

즉, O(Q×(V+E))

V와 E는 각각 최대 5000과 4999가 되지만 5000으로 생각해주었고, Q는 최대 5000
즉, (5000x(5000x4999)) = 5 x 10^7 < 10^8

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * 
 * @author juyoung
 * 질문 개수(Q)만큼 반복문 실행
 * 각 경우(시작 영상 정점은 v)마다 영상 now와 연결돼있는 영상과의 USADO 집합을 돌면서
 * 문제 조건에 맞는 경우에만(방문하지 않은 정점 && 해당 정점의 USADO값이 k 이상인 경우) count++
 * 그 다음 질문 탐색 
 * P : int N(영상 정점 개수), Q(질문 개수), p(정점), q(정점), r(USADO), k(기준), v(현재 시청 영상 정점)
 * R : 각 질문에 대한 답, 기준이 k고 현재 v번 영상을 시청할 때 k 이상이 되는 영상(정점)의 개수
 */

/* 정점, USADO */
class Node{
	int idx, val;
	
	public Node(int idx, int val) {
		this.idx = idx;
		this.val = val;
	}
}
public class Main {

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

		st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken()); // 영상 개수
		int Q = Integer.parseInt(st.nextToken()); // 질문
		
		ArrayList<Node>[] graph = new ArrayList[N+1];
		
		for(int i=1; i<=N; i++) {
			graph[i] = new ArrayList<>();
		}
		
		/* (정점, USADO)를 graph에 추가 */
		for(int i=0; i<N-1; i++) {
			st = new StringTokenizer(br.readLine());
			
			int p = Integer.parseInt(st.nextToken());
			int q = Integer.parseInt(st.nextToken());
			int r = Integer.parseInt(st.nextToken());
			
			graph[p].add(new Node(q, r));
			graph[q].add(new Node(p, r));
			
		}
				
		// 질문
		for(int i=0; i<Q; i++) {
			st = new StringTokenizer(br.readLine(), " ");

			// 기준이 되는 K가 k일 때 영상 v를 보고 있는 경우
			int k = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			int count = 0;
			
			Queue<Integer> queue = new LinkedList<>();
			boolean[] visited = new boolean[N+1];
			
			visited[v] = true;
			queue.add(v);
			
			while(!queue.isEmpty()) {
				int now = queue.poll();
				
				List<Node> list = graph[now]; // 영상 now와 연결돼있는 영상과의 USADO 집합
				
				for(int j=0; j<list.size(); j++) {
					
					if(!visited[list.get(j).idx] && list.get(j).val >= k) {
						// 문제 조건에 맞는 경우
						count++;
						queue.add(list.get(j).idx);
						visited[list.get(j).idx] = true;
					}
				}
			}
			sb.append(count+"\n");
		}
		
		System.out.println(sb);
	}
}