[BAEKJOON(백준)] 15591. MooTube (Silver)

www.acmicpc.net/problem/15591

15591번: MooTube (Silver)

---

문제

노드와 엣지가 주어진다

엣지에는 가중치가 있다

모든 동영상 사이에는 서로 얼마나 가까운지를 측정하는 단위인 'USADO' 값을 가진다

그리고 그 값이 주어진 K보다 크면 추천해줄 수 있다

(주어지지 않은 USADO 구하는 방법은 위 문제 링크를 통해 확인할 수 있다 - 문제가 길고 복잡해 생략한다)

예를 들어 k=1, start=2가 주어지면,

2번 동영상과 가까운 동영상 중 USADO가 1이상인 동영상은 몇 개인가? 

k=3, start=1이 주어지면,

1번 동영상과 가까운 동영상 중 USADO가 3이상인 동영상은 몇 개인가?

해결

주어진 숫자의 노드와 엣지를 통해 그래프를 그렸다

그리고 출발 노드를 스택에 넣고 이어진 노드를 하나씩 꺼내어 가중치와 주어진 K를 비교한다

K보다 작다면 추천할 수 없으므로 제외, 크거나 같다면 result 값을 1씩 더해준다

그리고 최종적으로 result를 출력한다

 

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());

        Graph graph = new Graph(n);

        for (int i=0; i<n-1; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            graph.addEdge(node1, node2, weight);
        }

        for (int i=0; i<q; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int k = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            System.out.println(graph.dfs(k, s));
        }
    }

    static class Graph {
        private int node;
        private LinkedList<Edge>[] adjacencylist;

        public Graph(int node) {
            this.node = node;
            this.adjacencylist = new LinkedList[node+1];
            for (int i=0; i<=node; i++) adjacencylist[i] = new LinkedList<>();
        }

        public void addEdge(int node1, int node2, int weight) {
            Edge edge = new Edge(node1, node2, weight);
            Edge edge2 = new Edge(node2, node1, weight);
            adjacencylist[node1].addFirst(edge);
            adjacencylist[node2].addFirst(edge2);
        }

        public int dfs(int k, int s) {
            int result = 0;
            Stack<Integer> stack = new Stack<>();
            boolean[] visited = new boolean[node+1];

            visited[s] = true;
            stack.add(s);
            while (!stack.isEmpty()) {
                int pop = stack.pop();

                Iterator<Edge> iterator =  adjacencylist[pop].listIterator();
                while (iterator.hasNext()) {
                    Edge nextEdge = iterator.next();
                    int next = nextEdge.node2;
                    int weight = nextEdge.weight;

                    if (!visited[next] && weight >= k) {
                        visited[next] = true;
                        stack.add(next);
                        result++;
                    }
                }
            }

            return result;
        }
    }

    static class Edge {
        int node1;
        int node2;
        int weight;

        public Edge(int node1, int node2, int weight) {
            this.node1 = node1;
            this.node2 = node2;
            this.weight = weight;
        }
    }
}