[JAVA] BOJ(백준) - MooTube (Silver) - 15591 - 자바

문제내용

https://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. 각 정점에서 모든 정점까지 연결된 가중치 중 최소 가중치 -> 플로이드 알고리즘 변형으로 푼다.

2. v1 에서 v2로 연결된 경로 반드시 하나존재, 모든 정점이 이어짐, n-1개의 간선을 갖고있음 -> 사이클이 없다 -> MST인지는 모르겠으나 스패닝 트리는 맞다 -> BFS or DFS 푼다.

 

이렇게 두가지 생각을 하게됐고 플로이드 알고리즘은 기본적으로 O(N^3)의 시간복잡도를 갖고있어서 입력값이 최대 5000인 문제에선 시간초과가 날꺼라고 생각은 했다. 그래도 플로이드를 활용해서 풀어봤고, 정답은 나오지만 시간초과.

그래서 다시 두번째 생각으로 풀이를 했다.

 

두번째 풀이에서 인지하고 풀어야 할부분이 있다.

먼저 유사도는 연결된 정점들의 최소 가중치를 나타낸다.

따라서 v와 연결된 정점 v2가 있을때 만약 유사도가 k보다 작다면 그뒤로 v2와 연결된 모든 정점은 k보다 낮은 유사도를 갖고 있기 때문에 v와 연관동영상으로 추천되지 않는다는 점을 알아야한다.

이점을 인지하고 유사도가 k이상인 것들만 추리면서 BFS로 탐색해내면 되고, 풀기위한 순서는 아래와같다.

 

(정점==영상)

1. 정점과 간선을 저장할 인접리스트 생성하고 저장.

2. 한번이라도 연산이 수행된 정점을 방문처리할 배열.

3. 큐에 초기값 삽입(입력값의 질문으로 주어짐) 및 방문처리.

4. BFS 시작 -> k이상인 것들만 카운트 , 큐에 추가 , 방문처리.

 

코드를 보자.

---

풀이

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 Main {
	static private int n,q;
	static private ArrayList<ArrayList<Node>> list = new ArrayList<ArrayList<Node>>();//정점,간선저장 리스트
	static private class Node{
		int v;
		int cost;
		public Node(int v, int cost) {
			this.v = v;
			this.cost = cost;
		}
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		q = Integer.parseInt(st.nextToken());
		
		//n+1개의 방만들기(0번 정점은 제외하기 때문에 n+1)
		for(int i=0; i<=n; i++)
			list.add(new ArrayList<Node>());
		
		//n-1개 만큼 정점 및 간선 표현
		for(int i=0; i<n-1; i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			
			//양방향
			list.get(v1).add(new Node(v2,cost));
			list.get(v2).add(new Node(v1,cost));
		}
		
		//질문 개수만큼 답해주고 출력.
		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());
			sb.append(findVideo(k, v)).append("\n");
		}
		System.out.println(sb.toString());
	}
	
	//질문의 v영상과 k이상 연관된 동영상 전부 찾고, 개수 반환.
	public static int findVideo(int k, int v) {
		Queue<Node> q = new LinkedList<>();
		boolean[] check = new boolean[n+1];
		q.add(new Node(v, Integer.MAX_VALUE));//질문 영상추가
		check[v] = true;//질문 영상확인
		
		int cnt = 0, linkMinCost = 0;
		//v와 k이상 연관된 영상 모두 찾기. 
		while(!q.isEmpty()) {
			Node cur = q.poll();//현재 영상
			ArrayList<Node> link = list.get(cur.v);//연결된 영상들
			
			//연결된 영상들 모두 탐색(foreach문으로 해도 상관없음)
			for(int i=0; i<link.size(); i++) {
				//이미 확인한 영상은 제외
				if(check[link.get(i).v]) continue;
				
				//현재 영상과 연결된 영상의 최소 유사도.
				linkMinCost = Math.min(link.get(i).cost, cur.cost);
				
				//k이상 연관된 영상만 아래의 조건문을 실행한다.
				//따라서 현재 연결된 영상의 유사도가 k보다 작아진다면,
				//그 뒤로 연결된 모든 영상은 k보다 작아진다는 뜻이된다. (유사도는 최소값이므로)
				//그러면 나는 그냥 유사도가 k이상되는것만 확인하면서 큐에 추가 후 반복해주면 된다.
				if(linkMinCost>=k) {
					check[link.get(i).v] = true;//영상 확인
					cnt++;//연결된 영상 카운트 추가
					q.add(new Node(link.get(i).v,linkMinCost));//큐에는 연결된 영상 정보 추가
				}
			}
		}
		return cnt;
	}
}

---

마치며

이번 문제는 그래프에 대한 문제로, 인접리스트를 활용하는 문제였다. 이전에 풀었던것과 비슷한 문제라서 구현을 하는데 어렵진 않았다. 만약에 코드를 보고 이해가 안된다면 먼저 인접리스트를 활용하는 그래프문제들을 먼저 풀어보는게 좋을꺼라고 생각한다.