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

1. 문제

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

15591번: MooTube (Silver)

 

 

2. 풀이 과정

방법 1. bfs

그래프는 MST로 주어지기 때문에, 인접리스트로 입력을 받았다.구현 방식은 매 query마다 bfs탐색을 하며, 가중치가 k이상인 경우만 더 탐색하도록 한다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;
import java.util.Queue;

public class Main {
    static int N;
    static ArrayList<int[]> adjlist[];

    public static int bfs(int k, int v){
        Queue<Integer> q = new LinkedList<>();
        boolean visited[] = new boolean[N+1];
        q.add(v);
        visited[v] = true;
        int result = -1;

        while(!q.isEmpty()){
            int now = q.poll();
            result++;
            for(int next[] : adjlist[now]){
                if(visited[next[0]] || next[1] < k){ continue;}
                visited[next[0]] = true;
                q.add(next[0]);
            }
        }
        return result;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());

        adjlist = new ArrayList[N+1];

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

        for(int i=1; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            adjlist[n1].add(new int[]{n2, c});
            adjlist[n2].add(new int[]{n1, c});
        }

        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(bfs(k, v)).append("\n");
        }
        System.out.println(sb);
    }
}

 

결과

 

방법 2. MST

간선 중심의 풀이 방식으로 Edge와 Query를 k중심으로 내림차순 정렬한다.

가중치가 k이상인 것만 union연산을 하면서, 이어진 그래프에서 노드 수는 root노드에 저장해두고 결과를 출력한다.

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

public class Main {
    static int N, parent[], count[];
    static ArrayList<int[]> adjlist[];

    static class Edge implements Comparable<Edge> {
        int s, e, c;

        public Edge(int s, int e, int c){
            this.s = s;
            this.e = e;
            this.c = c;
        }

        @Override
        public int compareTo(Edge o) {
            return o.c - this.c;
        }
    }
    static class Query implements Comparable<Query> {
        int k, v, order;//입력순서

        public Query(int k, int v, int order){
            this.k = k;
            this.v = v;
            this.order = order;
        }

        @Override
        public int compareTo(Query o) {
            return o.k - this.k;
        }
    }

    public static int find(int n1){
        if(parent[n1]==0){
            return n1;
        }
        return parent[n1] = find(parent[n1]);
    }

    public static void union(int n1, int n2){
        n1 = find(n1);
        n2 = find(n2);
        if(n1 != n2){
            count[n1] += count[n2];
            parent[n2] = n1;
        }
    }


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());
        parent = new int[N+1];
        count = new int[N+1];
        Arrays.fill(count, 1);

        Edge edges[] = new Edge[N-1];

        for(int i=0; i<N-1; i++){
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            edges[i] = new Edge(n1, n2, c);
        }

        Arrays.sort(edges);

        Query quries[] = new Query[Q];
        for(int i=0; i<Q; i++){
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            quries[i] = new Query(k, v, i);
        }
        Arrays.sort(quries);

        int idx = 0, result[] = new int[Q];
        for(Query q : quries){
            while(idx<N-1 && edges[idx].c >= q.k){
                union(edges[idx].s, edges[idx].e);
                idx++;
            }
            result[q.order] = count[find(q.v)]-1;
        }

        StringBuilder sb = new StringBuilder();
        for(int res : result){
            sb.append(res).append("\n");
        }
        System.out.println(sb);
    }
}

 

결과