[백준] 15591 MooTube (Silver) - 그래프 + DFS + BFS JAVA

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

15591번: MooTube (Silver)

코드설명

그래프탐색 문제에 DFS 혹은 BFS 를 사용합니다.

저는 DFS를 활용했습니다. BFS를 활용하여 Queue를 이용해도 됩니다.

 

처음에 문제에 나온 USADO가 최소값으로 결정된다는 점을 인지하지 못했다가, 이후에 확인했습니다.

 

시간복잡도를 계산해보겠습니다.

인접리스트로 DFS를 구현했을경우 시간복잡도는 O(N + e) 입니다. DFS가 모든 정점 N개를 한번씩 다 방문하고, 모든 간선을 한번씩 모두 검사했다고 한다면, O(N + e) 입니다. 이 문제에서는 Q만큼 반복합니다. 그러므로 O(Q * (N+e)) 가 시간복잡도가 됩니다. 

N는 정점의 개수, e는 간선의 개수를 의미합니다.

문제 조건에 (1 ≤ N ≤ 5,000), (1 ≤ Q ≤ 5,000), 즉 O(5000 * (5000 + 4999) ) 의 시간복잡도가 나옵니다. 

해당 시간복잡도를 계산하면 49,999,500 으로써 조금 반올림하여 5 * 10,000,000 이 나옵니다. 이는 오천만의 시간복잡도가 나옴으로써, 약 0.5초 안에 해결할 수 있습니다.

 

코드

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


public class Main {
	
	public static int N, Q;
	public static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
	public static boolean[] visited;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	Q = Integer.parseInt(st.nextToken());
    	
    	for(int i=0;i<=N;i++) { graph.add(new ArrayList<Node>()); }
    	visited = new boolean[N+1];
    	
    	for(int i=0;i<N-1;i++) {
    		st = new StringTokenizer(br.readLine());
    		int p = Integer.parseInt(st.nextToken());
    		int q = Integer.parseInt(st.nextToken());
    		int r = Integer.parseInt(st.nextToken());
    		
    		graph.get(p).add(new Node(q, r));
    		graph.get(q).add(new Node(p, r));
    	}
    	
    	for(int i=0;i<Q;i++) {
    		visited = new boolean[N+1];
    		st = new StringTokenizer(br.readLine());
    		int k = Integer.parseInt(st.nextToken());
    		int v = Integer.parseInt(st.nextToken());
    		
    		answer = 0;
    		visited[v] = true;
    		simulate(k, v, Integer.MAX_VALUE);
    		System.out.println(answer);
    	}
    	
    }
    
    public static void simulate(int K, int v, int minDistance) {
    	
    	for(int i=0;i<graph.get(v).size();i++) {
    		Node node = graph.get(v).get(i);
    		int compareDistance = minDistance;
    		compareDistance = Math.min(compareDistance, node.distance); //각 탐색마다 최소 Distance 를 구해야합니다.
    		
    		if(visited[node.nodeB] == true) continue; //이미 방문한적잇다면 continue;
    		if(compareDistance < K) continue; //USADO가 K보다 작다면 안됨 
    		
    		visited[node.nodeB]= true;
    		answer += 1;
    		simulate(K, node.nodeB, compareDistance);
    	}
    	
    }
    
}

class Node{
	int nodeB;
	int distance;
	public Node(int nodeB, int distance) {
		this.nodeB = nodeB;
		this.distance = distance;
	}
}