[백준]#15991 MooTube(Silver)
문제
농부 존은 남는 시간에 MooTube라 불리는 동영상 공유 서비스를 만들었다. MooTube에서 농부 존의 소들은 재밌는 동영상들을 서로 공유할 수 있다. 소들은 MooTube에 1부터 N까지 번호가 붙여진 N (1 ≤ N ≤ 5,000)개의 동영상을 이미 올려 놓았다. 하지만, 존은 아직 어떻게 하면 소들이 그들이 좋아할 만한 새 동영상을 찾을 수 있을지 괜찮은 방법을 떠올리지 못했다.
농부 존은 모든 MooTube 동영상에 대해 “연관 동영상” 리스트를 만들기로 했다. 이렇게 하면 소들은 지금 보고 있는 동영상과 연관성이 높은 동영상을 추천 받을 수 있을 것이다.
존은 두 동영상이 서로 얼마나 가까운 지를 측정하는 단위인 “USADO”를 만들었다. 존은 N-1개의 동영상 쌍을 골라서 직접 두 쌍의 USADO를 계산했다. 그 다음에 존은 이 동영상들을 네트워크 구조로 바꿔서, 각 동영상을 정점으로 나타내기로 했다. 또 존은 동영상들의 연결 구조를 서로 연결되어 있는 N-1개의 동영상 쌍으로 나타내었다. 좀 더 쉽게 말해서, 존은 N-1개의 동영상 쌍을 골라서 어떤 동영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재하도록 했다. 존은 임의의 두 쌍 사이의 동영상의 USADO를 그 경로의 모든 연결들의 USADO 중 최솟값으로 하기로 했다.
존은 어떤 주어진 MooTube 동영상에 대해, 값 K를 정해서 그 동영상과 USADO가 K 이상인 모든 동영상이 추천되도록 할 것이다. 하지만 존은 너무 많은 동영상이 추천되면 소들이 일하는 것이 방해될까 봐 걱정하고 있다! 그래서 그는 K를 적절한 값으로 결정하려고 한다. 농부 존은 어떤 K 값에 대한 추천 동영상의 개수를 묻는 질문 여러 개에 당신이 대답해주기를 바란다.
입력
입력의 첫 번째 줄에는 N과 Q가 주어진다. (1 ≤ Q ≤ 5,000)
다음 N-1개의 줄에는 농부 존이 직접 잰 두 동영상 쌍의 USADO가 한 줄에 하나씩 주어진다. 각 줄은 세 정수 를 포함하는데, 이는 동영상 와 가 USADO 로 서로 연결되어 있음을 뜻한다.
다음 Q개의 줄에는 농부 존의 Q개의 질문이 주어진다. 각 줄은 두 정수 을 포함하는데, 이는 존의 i번째 질문이 만약 라면 동영상 를 보고 있는 소들에게 몇 개의 동영상이 추천될 지 묻는 것이라는 것을 뜻한다.
출력
Q개의 줄을 출력한다. i번째 줄에는 농부 존의 i번째 질문에 대한 답변이 출력되어야 한다.
예제 입력 1
4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 1
예제 출력 1
3
0
2
풀이
이 문제는 알고리즘을 이용해서 풀 수 있었다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int N;
static ArrayList<Node>[] map;
static int[][] graph;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str = br.readLine().split(" ");
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(str[0]);
int Q = Integer.parseInt(str[1]);
graph = new int[N+1][N+1];
map = new ArrayList[N+1];
for(int i=1; i<=N; i++)
map[i] = new ArrayList<>();
for(int i=0; i<N-1; i++) {
String[] input = br.readLine().split(" ");
int start = Integer.parseInt(input[0]);
int end = Integer.parseInt(input[1]);
int cost = Integer.parseInt(input[2]);
map[start].add(new Node(end, cost));
map[end].add(new Node(start, cost));
}
for(int i=1; i<=N; i++)
bfs(i);
for(int i=0; i<Q; i++) {
String[] input = br.readLine().split(" ");
int K = Integer.parseInt(input[0]);
int start = Integer.parseInt(input[1]);
int cnt = 0;
for(int j=1; j<=N; j++) {
if(graph[start][j]>=K && start!=j) cnt++;
}
sb.append(cnt+"\n");
}
System.out.print(sb.toString());
}
public static void bfs(int start) {
Queue<Node> queue = new LinkedList<>();
boolean[] visited = new boolean[N+1];
visited[start] = true;
queue.add(new Node(start, Integer.MAX_VALUE));
while(!queue.isEmpty()) {
Node temp = queue.poll();
for(Node n : map[temp.end]) {
if(!visited[n.end]) {
visited[n.end] = true;
int min = Math.min(temp.cost, n.cost);
graph[n.end][start] = min;
graph[start][n.end] = min;
queue.add(new Node(n.end, min));
}
}
}
}
public static class Node {
int end;
int cost;
public Node(int end, int cost) {
this.end = end;
this.cost = cost;
}
}
}
Author And Source
이 문제에 관하여([백준]#15991 MooTube(Silver)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@pss407/백준15991-MooTubeSilver저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)