[Java] 백준 BOJ / 15591번: MooTube (Silver)

MooTube (Silver)

문제

문제 설명

N개의 동영상이 있고 동영상 끼리의 유사도 가 주어지는데 영상끼리의 유사도가 K 이상이라면 해당 영상은 추천동영상이 된다고 할때 K와 어떤 동영상의 번호 V가 주어지면 V 동영상의 추천 동영상은 몇개인지 출력하는 프로그램이다.

구현

일단 유사도를 저장하기 위해 Usado 라는 클래스를 만들었다. 이 클래스는 노드의 번호와 가중치를 저장한다.
이 노드는 각 노드마다 배열 형태로 저장되게 하였다.

class Usado{
  int node;
  int weight;

  public Usado(int node, int weight) {
    this.node = node;
    this.weight = weight;
  }
}

List<Usado>[] nodes = new ArrayList[n + 1];

for (int i = 1; i <= n; i++) {
  nodes[i] = new ArrayList<>();
}

그리고 양방향 간선이기 때문에 이후에 입력받는 값들을 양방향으로 저장해준다.

그 후에는 일반적인 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.List;
import java.util.Queue;
import java.util.StringTokenizer;

class Usado{
  int node;
  int weight;

  public Usado(int node, int weight) {
    this.node = node;
    this.weight = weight;
  }
}
public class Main_15591 {
  static int n, q;
  static List<Usado>[] nodes;
  static int k, v;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    StringBuilder sb = new StringBuilder();

    n = Integer.parseInt(st.nextToken());
    q = Integer.parseInt(st.nextToken());

    nodes = new ArrayList[n + 1];

    for (int i = 1; i <= n; i++) {
      nodes[i] = new ArrayList<>();
    }

    // 노드 정보 입력
    for (int i = 0; i < n - 1; i++) {
      st = new StringTokenizer(br.readLine());
      int start = Integer.parseInt(st.nextToken());
      int end = Integer.parseInt(st.nextToken());
      int weight = Integer.parseInt(st.nextToken());

      nodes[start].add(new Usado(end, weight));
      nodes[end].add(new Usado(start, weight));
    }

    //쿼리
    for (int i = 0; i < q; i++) {
      st = new StringTokenizer(br.readLine());

      k = Integer.parseInt(st.nextToken());
      v = Integer.parseInt(st.nextToken());

      boolean[] visited = new boolean[n + 1];
      visited[v] = true;
      Queue<Integer> queue = new LinkedList<>();
      queue.add(v);

      int answer = 0;
      while (!queue.isEmpty()) {
        int cur = queue.poll();

        for (Usado usado : nodes[cur]) {
          if (!visited[usado.node] && usado.weight >= k) {
            queue.add(usado.node);
            visited[usado.node] = true;
            answer++;
          }
        }
      }
      sb.append(answer).append('\n');
    }
    System.out.println(sb);
  }
}