[ 백준 / 15991 번 ] MooTube (Silver) - Java로 품

www.acmicpc.net/problem/15591

15591번: 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가 한 줄에 하나씩 주어진다. 각 줄은 세 정수 pi, qi, ri (1 ≤ pi, qi ≤ N, 1 ≤ ri ≤ 1,000,000,000)를 포함하는데, 이는 동영상 pi와 qi가 USADO ri로 서로 연결되어 있음을 뜻한다.

다음 Q개의 줄에는 농부 존의 Q개의 질문이 주어진다. 각 줄은 두 정수 ki와 vi(1 ≤ ki ≤ 1,000,000,000, 1 ≤ vi ≤ N)을 포함하는데, 이는 존의 i번째 질문이 만약 K = ki라면 동영상 vi를 보고 있는 소들에게 몇 개의 동영상이 추천될 지 묻는 것이라는 것을 뜻한다.

출력

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

힌트

농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 USADO는 min(3,2)=2가 되고, 1번 동영상과 4번 동영상의 USADO는 min(3,4)=3이 되고, 3번 동영상과 4번 동영상의 USADO는 min(2,4)=2가 된다.

농부 존은 K=1일 때 2번 동영상, K=3일 때 1번 동영상, K=4일 때 1번 동영상을 보면 각각 몇 개의 동영상이 추천될까 궁금해하고 있다. K=1일 때 2번 동영상에서 추천되는 동영상은 1, 3, 4번 동영상이다. K=4일 때 1번 동영상으로부터 추천되는 동영상은 없다. 그러나 K=3일때는 1번 동영상에서 2번 동영상과 4번 동영상이 추천된다.

 

풀이코드 

package newProject;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class MooTube {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int Q = Integer.parseInt(st.nextToken());
		ArrayList<int[]> [] al  = new ArrayList[N+1];
		for(int i =1; i <= N; i++) {
			al[i] = new ArrayList<int[]>();
		}
		for(int i =1 ; i< N; i++) {
			st = new StringTokenizer(br.readLine());
			int p  = Integer.parseInt(st.nextToken());
			int q = Integer.parseInt(st.nextToken());
			int r  = Integer.parseInt(st.nextToken());
			al[p].add(new int[] {q,r});
			al[q].add(new int[] {p,r});
		}
		StringBuilder sb = new StringBuilder();
		for(int i =0; i< Q ; i++) {
			st = new StringTokenizer(br.readLine());
			int K = Integer.parseInt(st.nextToken());
			int V = Integer.parseInt(st.nextToken());
			int cnt = 0; 
			Queue<Integer> q = new LinkedList<Integer>();
			boolean[] v = new boolean[N+1];
			v[V] = true;
			q.offer(V);
			while(!q.isEmpty()) {
				int t = q.poll();
				for(int[] a : al[t]) {
					if(!v[a[0]] && a[1]>=K ) {
						cnt++;q.offer(a[0]);
						v[a[0]]= true;
					}
				}
			}
			sb.append(cnt).append("\n");
			
		}
		System.out.println(sb);
	}
}

 

 문제 해석이 너무 번거롭다..

처음에는 문제 보고 다익스트라인줄 알았다. 아니더라.. 그리고서는 머리가 하도 안돌아가서 주변에서 힌트를 좀 얻어다가 풀었다.  안푼지 너무 오래되서 그런지 머리가 안돌아간다. 

여기서 메인으로 사용하는 방법은 

BFS를 사용해 연결된 모든 연결된 USADO를 구한다(유사도도 왜 영어로 써놓은거지.. 번거롭게..)

거기에 유사도는 무조건 더 BFS의 depth가 커질수록 작아지게 된다(min을 취하기 떄문에) 

K보다 큰 유사도를 가진 노드만 BFS에 포함시킨다. 

번역 본이라 그런가..

차근 차근 이제 코드 풀이를 한다. 

입력부는 생략하고, 

ArrayList배열을 만든다. 힌트를 보니 배열로 풀면 시간초과가 난다고 한다. 그러므로 나는 바로 ArrayList로 구현하였다.

1번부터 N번까지 있으므로 N+1개의 ArrayList배열을 만든다. 

이후에는 p,q,r값을 받으면서 이를 ArrayList에 저장해 준다. 

이거는 나중에 출력문이 몇줄이 될지 모르니 StringBuilder로 만들어서 시간을 줄일수 있게 하였다.

그리고 나서 Q개의 개수를 받아서 출력할 수 있도록 한다.

K, V가 

K : 출력할 유사도 마지노석

V : 몇번째 를 시청하였는지 == 시작점 

 

이렇게 우선 cnt 라고 몇개가 유사도가 넘는지를 세어줄 변수cnt를 선언한다. 

그리고 Queue q를 통해 BFS를 돌 수 있도록 한다. 

먼저 돌기 전에, 무한 반복되지 않도록 항상 bfs는 방문 여부인 visited(v)를 선언해 주어야 한다. N+1의 boolean배열로 선언해주고, 

v[V] = true로 이미 값이 있다는 것을 체크해준다.

그리고 시작점인 V를 q에 넣고, BFS를 돌린다. 

( queue에는 add보다 offer를쓰는 것이 속도가 좀 더 낫다고 들었다. ) 

while( ! q.isEmpty() ) 를 통해 반복하게 되는데, 

시작 점인 t를 먼저 poll로 뺴고, 

그 t의 노드에 연결된 점들을 반복해서 유사도를 찾는다.

유사도를 찾아서 해야할 일은 만약 이 값이 시작점과 연결이 되어 있고, 그 값이 이전에 이미 방문되어 있는 값이 아니고, 또한 그 값의 유사도가 a[1]에 저장되어있는데, 

이 값이 K보다 크거나 같다면, 

cnt를 추가한다.

그리고q.offer(a[0])으로 queue에도 추가해주는데, 여기서 중요한 점이다.

min으로 처리되기 떄문에 k보다 작은 값이 들어온다면 그 값은 다시 돌아와서 어떻게 구하든 더 커질 수 없다. 그래서 작으면 다 버리고, 크면 남기게 되면, 그 값이 유사도가 K보다 큰 값이 된다. 

그리고 이미 방문 하였으므로(가까운순) : v[a[0]]=true 로 방문 처리를 해주면 된다. 

그리고 마지막에 이 cnt값을 Stringbuilder에 추가시키면 된다. 

그리고 

 

출력하면 끝