BOJ - 15991

BOJ - 15991

(문제 : https://www.acmicpc.net/problem/15591)
(코드 참고 : https://bellog.tistory.com/128)

문제 해결 방법

1. 각 노드는 양방향성을 가지고 있으며, 각 edge 연관성(weight)의 최솟값을 구하여 k 이상일 경우 count하면 되는 알고리즘으로 생각함.
2. 만약 연관성(weight)이 k 미만일 경우에는 BFS를 실행하지 않는다.(불필요한 탐색 최소화)

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public static class Node{
		int end;
		long weight;
		
		Node(int end, long weight) {
			this.end = end;
			this.weight = weight;
		}
	}
	public static ArrayList<Node> list[];
	public static int N, Q;
	public static final long MAX = (long) 1_000_000_000 * (long) 5_001;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[N + 1];
		
		for(int i = 0; i <= N; i++) list[i] = new ArrayList<>();
		
		for(int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(br.readLine());
			
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			list[s].add(new Node(e, w));
			list[e].add(new Node(s, w));
		}
		
		for(int i = 0; i < Q; i++) {
			st = new StringTokenizer(br.readLine());
			
			long k = Long.parseLong(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			sb.append(dijkstra(k, v) + "\n");
		}
		
		System.out.print(sb.toString());
	}
	
	public static int dijkstra(long k, int v) {
		int answer = 0;
		ArrayDeque<Node> q = new ArrayDeque<>();
		
		q.add(new Node(v, MAX));
		boolean[] visited = new boolean[N + 1];
		visited[v] = true;
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			int curNode = node.end;
			long weight = node.weight;
			
			for(int i = 0; i < list[curNode].size(); i++) {
				if(visited[list[curNode].get(i).end]) continue;
				if(list[curNode].get(i).weight < k) continue;
				
				answer++;
				q.add(new Node(list[curNode].get(i).end, list[curNode].get(i).weight));
				visited[list[curNode].get(i).end] = true;
			}
		}
		
		return answer;
	}

}

후기

BFS 해결법에서 간선 탐색 중 최솟값을 넣는 방법을 생각했었는데 생각보다 쉽지가 않았다.
한 2시간 정도 붙잡고 테스트 케이스 통과 후 9%에서 막히고 다시 해봤지만 결과는 그대로였음.
코드 참고 후 방문 변수를 넣지 않아서 엉뚱한 답이 나온것 같음.