[백준 2610] 회의준비 (Java)

문제 링크: https://www.acmicpc.net/problem/2610

2610번: 회의준비

1. 주의할 점

- 출력값은 오름차순으로 출력되어야 한다

- 총 의사전달시간의 최소가 아닌 의사전달시간의 최대값의 최소(전체가 아닌 각각)

 

2. 구현

- Arr[][] 배열과 Check[] 배열을 초기화한 이후, 값을 입력 받는다

- 플로이드와샬 알고리즘을 통해 Arr[][] 배열을 갱신한다

- 1~Node번까지의 참석자들을 모두 탐색하며 Check[] 값이 False라면 DFS(idx) 함수를 수행하며 idx번째 참석자와 연결된 모든 참석자 중에서 Cal() 연산을 통해 의사전달시간의 최대값의 최소를 가진 aidx를 구하고 반환한다

- DFS() 함수를 통해 반환받은 값을 Li 리스트에 넣은 후, 오름차순 정렬을 수행한다

 

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    static final int maxi = 987654321;
    static int node,edge;
    static int arr[][];
    static boolean check[];
    
    static int cal(int idx){
        int cnt=0;
        for(int i=1;i<=node;i++){
            if(arr[idx][i]>0 && arr[idx][i]!=maxi) cnt=Math.max(cnt,arr[idx][i]);
        }
        return cnt;
    }
    
    static int dfs(int idx){
        List<Integer> li = new ArrayList<>();
        check[idx]=true;
        int aidx = idx;
        int mini=cal(idx);
        for(int i=1;i<=node;i++){
            if(check[i]) continue;
            if(arr[idx][i]>0 && arr[idx][i]!=maxi){      //연결된 다른 지점
                check[i]=true;
                int cnt = cal(i);
                if(mini>cnt){
                    mini=cnt;
                    aidx=i;
                }
            }
        }
        return aidx;
    }
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String str = br.readLine();
	    StringTokenizer st = new StringTokenizer(str);
	    node = Integer.parseInt(st.nextToken());
	    str = br.readLine();
	    st = new StringTokenizer(str);
	    edge = Integer.parseInt(st.nextToken());
	    
	    //초기화
	    arr = new int[node+1][node+1];
	    check = new boolean[node+1];
	    for(int i=1;i<=node;i++)
    	    for(int j=1;j<=node;j++){
    	        arr[i][j]= maxi;
    	        if(i==j)    arr[i][j]=0;
    	    }
    	        
	    for(int i=0;i<edge;i++){
	        str = br.readLine();
    	    st = new StringTokenizer(str);
    	    int a = Integer.parseInt(st.nextToken());
    	    int b = Integer.parseInt(st.nextToken());
    	    arr[a][b]=1;
    	    arr[b][a]=1;
    	}
    	for(int k=1;k<=node;k++)
    	    for(int i=1;i<=node;i++)
    	        for(int j=1;j<=node;j++)
    	            if(arr[i][j]>arr[i][k]+arr[k][j])
    	                arr[i][j]=arr[i][k]+arr[k][j];

        List<Integer> li = new ArrayList<>();
    	for(int i=1;i<=node;i++){
    	    if(check[i]==true) continue;
    	    li.add(dfs(i));
    	}
    	Collections.sort(li);
	    System.out.println(li.size());
		for(int i: li){
		    System.out.println(i);
		}
	}
}