1135 뉴스 전하기

 

예제를 가지고 설명하자면,

 

5

-1 0 0 2 2

 

다음과 같은 상황을 생각할 수 있다.

즉 민식이가 (루트 노트 0)  부하직원에게 연락을 하는데

(단, 직원들에게 동시에 연락할 수 없음)

 

1초 :  0번 노드 -> 2번 노드 직원

2초 :  0번 노드 -> 1번 노드 직원,

          2번 노드 -> 3번 노드  

3초 : 2번 노드 -> 4번 노드

 

 

 

 

위의 경우는 위에서 아래로 내려오며 시간 계산한 경우를 설명한 것이고,

 

문제 풀이는 아래에서 위로 시간 계산을 한다.

 

 

 

일단 트리 구조에 본인과 연결된 노드를 저장한다

tree[0] = 1,2

tree[1] = 없음

tree[2] = 3,4

tree[3] = 없음

tree[4] = 없음

 

dfs를 이용하는데,

0번 노드부터 시작한다.

 

그러면 0번 노드에서 시작해서,

자식 노드로 계속 내려가면서 dp값을 계산하는데,

 

1) 맨 아래에 있는 3번, 4번 노드

dp[3] = 0

dp[4] = 0

 

2) 2번 노드 

=> 우선순위 큐에 ( 자식 노드 번호, 자식 노드 dp값을 넣어줌)

=> 우선순위 큐 : (3,0) , (4,0)

그 이후 값을 1개씩 꺼내면서, 

dp 값에 1씩 (증가해가며) 더해서 max 값을 구한다.

 

[1]

즉 (3,0)을 꺼낸 뒤,

dp 값 + 1

= 0 + 1

= 1

즉, 위의 그림에서 보이듯이 2번 노드와 3번 노드가 연락할 경우 1초가 지나고

 

[2]

두번째로 (4,0)을 꺼내고

dp값 + 2

= 0 + 2 

=2

2번 노드와 4번 노드가 연락할 경우 2초가 된다. 

 

이 중 큰 값이 dp[2] 의 값이 된다.

즉, dp[2] = 2

 

3) 1번 노드 

1번 노드의 경우에도 자식 노드가 없으므로

dp[1] = 0 

 

4) 0번 노드

=> 우선순위 큐에 ( 자식 노드 번호, 자식 노드 dp값을 넣어줌)

=> 우선순위 큐 : (2,2) , (1,0)

=> 우선순위 큐는 dp 값 내림차순으로 정렬을 해준다.

 

[1]

즉 (2,2)를 꺼낸 뒤,

dp값 + 1

= 2+1 

= 3

즉,  0번 노드와 2번 노드가 연락할 경우 3초가 되고

 

[2]

즉 (1,0)을 꺼낸 뒤,

dp 값 + 2 

= 0 +2

= 2

즉, 0번 노드와 1번 노드가 연락하면 2초가 된다. 

 

즉, 우선순위 큐에서  dp 값 내림차순으로 정렬하는 이유는

dp + (1,2,3...) 이런식으로 

점점 더해지는 값이 커지는데,

부하직원이 많은 쪽에 더 작은 값을 더하여 시간을 짧게 부여하기 위함이다.

 

이 때

2와 3 중에서 큰 값이 dp[0] 값이다.

즉 dp[0] = 3

 

이 경우 3이 정답이다.

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
 
	static ArrayList<Integer>[] tree;
	static int dp[];
	
    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());          
          
          dp = new int[N];          
          tree = new ArrayList[N];
          
          for(int i=0; i<N; i++) {
        	  
        	  tree[i] = new ArrayList<>();        	  
          }                 
          
          st = new StringTokenizer(br.readLine(), " ");   
          
          for(int i =0; i<N; i++) {        	  
        	  int number = Integer.parseInt(st.nextToken());
        	  
        	  if (number ==-1) {        		  
        		  continue;   
        		  
        	  }else {      		        		  
        		  tree[number].add(i);
        	  }       	  
          }
          
          
          System.out.println(dfs(0));       
        
    }
    
    public static int dfs(int index) {   	
    	
    	int max = 0;    	
    	
    	PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int []>() {
    		
    		@Override
    		public int compare(int a[], int b[]) {    			
    			return b[1] - a[1];    			
    		}    		
    	});  	
    	
    	
    	for(int next: tree[index]) {    		
    		dp[next] = dfs(next);    		
    		pq.add(new int[]{next,dp[next]});    		
    		
    	}
    	
    	
    	int count = 0;    	
    
    	while(!pq.isEmpty()) {
    		
    		int node[] = pq.poll();		
    		count++;    		
    		max = Math.max(max, node[1]+ count);
    	
    	}
    	   	
    	return max;	
    	
    }
}

 

 

 

 

참고 블로그 : https://ohksj77.tistory.com/213

백준 1135 자바 - 뉴스 전하기