BOJ - 15991
BOJ - 15991
(문제 : https://www.acmicpc.net/problem/15591)
(코드 참고 : https://bellog.tistory.com/128)
문제 해결 방법
- 각 노드는 양방향성을 가지고 있으며, 각 edge 연관성(weight)의 최솟값을 구하여 k 이상일 경우 count하면 되는 알고리즘으로 생각함.
- 만약 연관성(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%에서 막히고 다시 해봤지만 결과는 그대로였음.
코드 참고 후 방문 변수를 넣지 않아서 엉뚱한 답이 나온것 같음.
Author And Source
이 문제에 관하여(BOJ - 15991), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@qudgnl0422/BOJ-15991저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)