[백준 / Java] 11591번: Mootube (Silver) (골드5)

문제 풀이 날짜: 2023.09.08
포스트 작성일: 2023.09.11

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 11591번: Mootube (Silver) (골드5)

 

키워드

BFS, 최소 신장 트리

 

풀이 접근법

• 최소 신장 트리(Spanning Tree)를 구하는 문제이다. 구현은 인접 리스트 그래프와 BFS로 하였다.
• 우선 인접하지 않은 모든 두 정점의 usado를 구한다.
  • BFS로 모든 점을 방문하면서 currStart와 연결되지 않은 정점을 발견하면 무조건 min을 넣어준다.
  • v번 정점과 연결된 모든 정점 중 usado가 k 이하인 것의 수를 센다.
• 가지치기를 하지 않으면 시간 초과가 나기 쉬우므로 주의한다.
  • K 이상인 정점의 수는 BFS 안에서 센다. (밖에서 세면 O(N^2) 만큼 더 소모)
  • graph를 Node 타입으로 선언하고, 그 안에 usado를 함께 저장한다.
  • usado가 K 이상인 정점만 큐에 넣어서 가지치기를 한다. 우리는 usado가 K 이상인 영상의 수만 세면 되며, 서로 연결되지 않은 두 정점의 usado는 그곳까지 가는 경로 중 최소인 것으로 결정된다.
  • (문제 3번 테케 참고) 만약 usado가 3이상인 것들만 찾는다고 했을 때, usado가 2인 정점을 넣어봤자 큐에 연결되지 않은 두 정점의 경로도 2로 초기화 된다. 그렇다고 해도 정답으로 카운트가 되지 않는다. 따라서 제외 시킨다.

 

코드

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

public class Main {

	private static int K;
	private static int count = 0;
	
	private static List<Node>[] graph;
	private static boolean[] visited;

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

		String[] input = br.readLine().split(" ");

		int N = Integer.parseInt(input[0]);
		int Q = Integer.parseInt(input[1]);

		graph = new LinkedList[N + 1];
		for (int i = 1; i <= N; i++) {
			graph[i] = new LinkedList<>();
		}
		
		visited = new boolean[N + 1];
		
		StringTokenizer st;
		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));
		}

		// 1.인접하지 않은 두 정점의 usado를 구한다.
		// 2.v번 간선과 연결된 모든 정점 중 usado가 k 이하인 것의 수를 센다.
		StringBuilder sb = new StringBuilder();
		for(int q = 0; q < Q; q++) { //O(N)
			st = new StringTokenizer(br.readLine());
			
			K = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			BFS(v); // O(V + E);
			
			sb.append(count).append("\n");
			
			count = 0;
			visited = new boolean[N + 1];
		}
		
		System.out.println(sb);
		
	}

	private static void BFS(int from) {
		Queue<Integer> queue = new ArrayDeque<>();
		
		queue.add(from);
		visited[from] = true;

		while (!queue.isEmpty()) {
			int v = queue.poll();
						
			for(Node u : graph[v]) {
				//가지치기 => 어떤 간선의 가중치가 K이상이어야만 큐에 넣는다.
				if(!visited[u.num] && u.usado >= K) {
					count++;

					visited[u.num] = true;
					queue.add(u.num);
				}
			}
		}
		
		return;
	}

}

class Node {
	int num; //연결된 노드
	int usado;
	
	public Node(int num, int usado) {
		this.num = num;
		this.usado = usado;
	}
}

---

 

git 링크

(git 링크 첨부)