백준 15591번: MooTube (Java)

접근

https://www.acmicpc.net/problem/15591

문제에서 주어진 두 영상 사이의 관계를 그래프로 저장해주고, 요청되는 질문에 대하여 k값보다 큰 관계들만 탐색되도록 bfs 탐색을 해주어 문제를 해결할 수 있었다. 문제는 어렵지 않았지만 왠지 문제의 의미를 이해하기 어려운 문제였다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

  static int N, Q, ans;
  static ArrayList<int[]>[] adj;
  static boolean visited[];

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String[] input = br.readLine().split(" ");
    N = Integer.parseInt(input[0]);
    Q = Integer.parseInt(input[1]);
    adj = new ArrayList[N + 1];

    for (int i = 1; i <= N; i++) {
      adj[i] = new ArrayList<>();
    }
    for (int i = 1; i < N; i++) {
      input = br.readLine().split(" ");
      int p = Integer.parseInt(input[0]);
      int q = Integer.parseInt(input[1]);
      int r = Integer.parseInt(input[2]);
      adj[p].add(new int[] { q, r });
      adj[q].add(new int[] { p, r });
    }

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < Q; i++) {
      input = br.readLine().split(" ");
      int k = Integer.parseInt(input[0]);
      int v = Integer.parseInt(input[1]);

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

      while (!queue.isEmpty()) {
        int cur = queue.poll();
        for (int[] a : adj[cur]) {
          if (!visited[a[0]] && a[1] >= k) {
            queue.add(a[0]);
            visited[a[0]] = true;
            ans++;
          }
        }
      }
      sb.append(ans).append('\n');
    }
    System.out.println(sb.toString());
    br.close();
  }
}

더 생각해 볼 것?

JAVA를 이용한 첫번째 문제 풀이여서인지 간단한 알고리즘도 헤매면서 풀었다. 앞으로 java에 더 익숙해져야겠다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!