[Java] BaekJoon 15591. MooTube(골드5) (그래프 탐색) (DFS) (BFS)

문제출처: https://www.acmicpc.net/problem/15591

15591번: MooTube (Silver)

 

문제이해

 

목표

N개의 동영상이 있다.
N - 1개의 간선(각 동영상간에 얼마나 가까운지)이 있다.
=> 그래프 

존은 N-1개의 동영상 쌍을 골라서 어떤 동영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재하도록 했다. 존은 임의의 두 쌍 사이의 동영상의 USADO를 그 경로의 모든 연결들의 USADO 중 최솟값으로 하기로 했다.
=> 두 노드간에 경로가 존재하는데, 그 경로의 간선중 최솟값이 USADO가 됨

존은 어떤 주어진 MooTube 동영상에 대해, 값 K를 정해서 그 동영상과의 USADO가 K 이상인 모든 동영상이 추천되도록 할 것이다. 동영상을 V를 보고 있는 소들에게 몇 개의 동영상이 추천될 수 있는 지 묻는다.
=> 출발 지점 V에서 다른 모든 비디오의 경로를 탐색하 때 해당 비드오의 USADO가 K이상이면 추천

 

예제 그림을 통해 이해

예제 그림

 

풀이

1. DFS
   Q개의 case별로 각각 V와 K 값을 받고 DFS로 탐색하는 방법이다. 
   
   (1) 인접리스트를 만든다. Edge class에는 도착지와 간선비용이 들어있다.
   (2) V와 K의 값을 받고 V에서 DFS를 시작한다. 
    -> DFS 도중 K값 미만인 경우는 더이상 탐색하지 않는다. 어차피 정답은 USADO가 K이상인 것만 체크하기 때문에 
    -> 탐색을 하는 경우에는 계속 갱신하면서 가져온 min값과 현재 간선의 비용을 비교해서 더 작은값으로 갱신하고 
        답을 저장하는 answer[edge.dest]도 갱신된 값으로 저장하여 준다. 
        (answer[i]는 V노드에서 출발하여 i번째 노드에 도착한 USADO 값이 저장된다)
   (3) answer[]의 값이 0보다 큰값을 count하여 답을 도출한다.
   
   
2. BFS
   case별로 DFS하지 않고 모든 노드에서 BFS 탐색을 시작하는 경우를 다 찾아보고 저장한 다음. 답을 출력하는 방법.
   
   (1) 인접리스트를 만든다. Edge class에는 도착지, 간선비용, 지금까지 갱신된 min 값이 들어있다.
   (2) 모든 노드가 출발지가 될 수 있는 모든 경우의 수로 BFS를 시작한다. 
    -> 방문했던 경우 탐색하지 않는다.
    -> 탐색을 하는 경우에는 계속 갱신하면서 가져온 min값과 현재 간선의 비용을 비교해서 더 작은값으로 갱신하고 
        답을 저장하는 answer[start][edge.dest]도 갱신된 값으로 저장하여 준다. 
        (answer[start][i]는 V(start)노드에서 출발하여 i번째 노드에 도착한 USADO 값이 저장된다)
   (3) V와 K를 입력받고 answer[V][]의 값이 k보다 큰값을 count하여 답을 도출한다.

 

소스코드

1. DFS

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

import static java.lang.System.in;

public class MooTube_DFS {

    static final int MAX = 1000000001;
    static boolean[] visited;
    private static ArrayList<Edge>[] adjList;
    private static int k;
    private static int[] answer;

    static class Edge {
        int dest;
        long price;

        public Edge(int dest, long price) {
            this.dest = dest;
            this.price = price;
        }
    }

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

        // 인접리스트 생성
        adjList = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            adjList[i] = new ArrayList<>();
        }
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()) - 1;
            int dest = Integer.parseInt(st.nextToken()) - 1;
            long price = Long.parseLong(st.nextToken());
            adjList[start].add(new Edge(dest, price));
            adjList[dest].add(new Edge(start, price));
        }
        // 정답출력
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());
            k = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken()) - 1;

            // dfs
            answer = new int[N];
            visited = new boolean[N];
            visited[v] = true;
            dfs(v, MAX);

            int count = 0;
            for (int videos : answer) {
                if (videos > 0) {
                    count++;
                }
            }
            sb.append(count).append("\n");
        }
        System.out.println(sb);
    }

    private static void dfs(int now, int min) {
        for (Edge edge : adjList[now]) {
            if (!visited[edge.dest] && edge.price >= k){ // 방문하지않고 k 이상일 때만 탐색하도록
                int m = (int) Math.min(min, edge.price);
                answer[edge.dest] = m;
                visited[edge.dest] = true;
                dfs(edge.dest, m);
            }
        }
    }
}

 

2. BFS

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

import static java.lang.System.in;

// BFS 풀이버전
public class MooTube_BFS {

    static final int MAX = 1000000001;

    static class Edge {
        int dest;
        long price;
        int min;

        public Edge(int dest, long price) {
            this.dest = dest;
            this.price = price;
            min = MAX;
        }

        public Edge(int dest, long price, int min) {
            this.dest = dest;
            this.price = price;
            this.min = min;
        }
    }

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

        // 인접리스트 생성
        ArrayList<Edge>[] adjList = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            adjList[i] = new ArrayList<>();
        }
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()) - 1;
            int dest = Integer.parseInt(st.nextToken()) - 1;
            long price = Long.parseLong(st.nextToken());
            adjList[start].add(new Edge(dest, price));
            adjList[dest].add(new Edge(start, price));
        }

        int[][] answer = new int[N][N];
        Queue<Edge> pq = new LinkedList<>();
        for (int start = 0; start < N; start++) {

            // bfs
            boolean[] visited = new boolean[N];
            visited[start] = true;
            Edge startEdge = new Edge(start, 0);
            pq.add(startEdge);

            while (!pq.isEmpty()) {
                Edge edge = pq.poll();
                for (Edge nextEdge : adjList[edge.dest]) { // 다음 노드로
                    if(!visited[nextEdge.dest]){
                        int min = (int) Math.min(edge.min, nextEdge.price);
                        pq.add(new Edge(nextEdge.dest, nextEdge.price, min));
                        answer[start][nextEdge.dest] = min;
                        visited[nextEdge.dest] = true;
                    }
                }
            }
        }

        // 정답출력
        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()) - 1;

            int count = 0;
            for (int videos : answer[v]) {
                if(videos >= k){
                    count++;
                }
            }
            sb.append(count).append("\n");
        }
        System.out.println(sb);

        for (int[] ints : answer) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }
}

 

실행 결과

K라는 제한이 있기 때문에 한꺼번에 탐색을 하고 정답을 도출하기 보다, 입력받은 K,V에 따라 탐색을 시작하여 정답을 도출하는게 더 바람직한 것 같다. (DFS, BFS의 차이 X)