백준 BOJ 15591 풀이 (JAVA)

 

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

15591번: MooTube (Silver)

 

오랜만에 백준 문제를 풀어보았습니다. 

문제 설명은 아래와 같습니다.

문제 설명

입력 예시는 아래와 같고, 친절하게 힌트까지 있습니다.

N개의 동영상이 있는데, N-1개의 쌍으로 네트워크를 만들었다는 것에서 트리 구조로 데이터를 표현해야 함을 알았습니다.

매 Question 마다 동영상 v에 대해 k이상인 경우에만 BFS 나 DFS로 간선을 탐색하면 될 것 같았습니다.

 

처음에는 Question의 수가 5000이기 때문에 N^2으로 작성해도 될까 싶어 인접행렬 형태로 트리를 모델링 해서 BFS로 제출했는데 당연히 시간초과가 났습니다.  

 

인접리스트로 다시 작성하려고 하니 JAVA에서는 C++에서처럼 쉽게  Pair나 Struct(구조체)가 것이 없어 node를 표현하는 Class를 만들고 맴버변수로는 node, weight를 설정했습니다.

 

그리고 매 question 마다, 해당 노드에서 BFS를 돌려서 탐색가능한 노드의 갯수 즉 추천된 동영상의 갯수를 리턴하여 문제를 해결했습니다.

 

소스코드 보기(JAVA) 👇

import java.io.FileInputStream;
import java.util.*;

public class Main {
    static class Node{
        int node;
        int weight;
        public Node(int _node, int _weight){
            this.node = _node;
            this.weight = _weight;
        }
    }
    static int video_refer_count(int k, int v, ArrayList<ArrayList<Node>> graph, int N){
        int [] visited =  new int[N+1];
        int count = 0;
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(v);
        visited[v] = 1;
        while(!q.isEmpty()){
            int current = q.poll();

            for(int i=0;i< graph.get(current).size(); i++){
                int weight = graph.get(current).get(i).weight;
                int node = graph.get(current).get(i).node;
                if(weight>=k && visited[node]==0 ){
                    q.add(node);
                    visited[node] = 1;
                    count++;
                }
            }

        }
        return count;
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int Q = sc.nextInt();
        ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
        for(int i=0; i<N+1; i++)
                graph.add(new ArrayList<Node>());
        for(int i=0; i<N-1; i++){
            int p = sc.nextInt();
            int q = sc.nextInt();
            int r = sc.nextInt();
            graph.get(p).add(new Node(q, r));
            graph.get(q).add(new Node(p, r));
        }


        for(int i=0; i<Q; i++){
            int k = sc.nextInt();
            int v = sc.nextInt();
            int answer  = video_refer_count(k, v, graph, N);
            System.out.println(answer);
        }

    }
}

오랜만에 문제를 알고리즘 문제를 풀어보니, 예전 생각도 나고 몰입도 되고 재밌었습니다.

자주 풀어야 겠습니다. 화이팅