https://www.acmicpc.net/problem/15591
저는 해당 문제를 BFS를 통해서 문제를 해결하였습니다.
처음 생각으로는 플루이드-워샬을 생각하였지만, 플루이드 워샬을 시간복잡도 O(n^3)이기 때문에 N의 범위를 보고 시간초과가 나올 것이라고 생각하였습니다.
저는 BFS를 하여 시작점부터 탐색해 가중치가 K보가 크다면 계속 진행하고 작다면 진행하지 않게 구현하여 문제를 해결하였습니다.
package BOJ.BFS;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.function.Function;
public class BOJ_15591 {
private static class Node{
int end;
int weight;
public Node(int end, int weight) {
this.end = end;
this.weight = weight;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
Function<String,Integer> stoi = Integer::parseInt;
int n = stoi.apply(st.nextToken());
int m = stoi.apply(st.nextToken());
List<Node>[] map = new ArrayList[n+1];
for(int i = 0 ; i <= n ; i++){
map[i] = new ArrayList<>();
}
for(int i = 0 ; i < n-1 ; i++){
st = new StringTokenizer(br.readLine()," ");
int a = stoi.apply(st.nextToken());
int b = stoi.apply(st.nextToken());
int c = stoi.apply(st.nextToken());
map[a].add(new Node(b,c));
map[b].add(new Node(a,c));
}
for(int i = 0 ; i < m ; i++){
st = new StringTokenizer(br.readLine()," ");
int a = stoi.apply(st.nextToken());
int b = stoi.apply(st.nextToken());
System.out.println(bfs(map,a,b,n));
}
}
private static int bfs(List<Node>[] map, int a, int b,int n) {
Queue<Integer> q = new LinkedList<>();
q.offer(b);
int result = 0;
boolean[] visited = new boolean[n+1];
visited[b] = true;
while(!q.isEmpty()){
int now = q.poll();
for(int i = 0 ; i < map[now].size(); i++){
Node next = map[now].get(i);
if(!visited[next.end] && next.weight >= a){
// System.out.println("next:"+next.end);
result++;
visited[next.end] = true;
q.offer(next.end);
}
}
}
return result;
}
}
'알고리즘' 카테고리의 다른 글
백준 17141번 연구소 2 (JAVA) (0) | 2022.02.19 |
---|---|
백준 16194번 카드 구매하기2 (JAVA) (0) | 2022.02.18 |
백준 2661번 좋은수열 (JAVA) (0) | 2022.02.15 |
백준 16929번 Two Dots (JAVA) (0) | 2022.02.14 |
백준 2217번 로프 (JAVA) (0) | 2022.02.13 |