어흥
[백준 2610] 회의준비 (Java) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/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);
}
}
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 11562] 백양로 브레이크 (Java) (0) | 2021.06.16 |
---|---|
[백준 1507] 궁금한 민호 (Java) (0) | 2021.06.16 |
[백준 2098] 외판원 순회 (Java) (0) | 2021.06.10 |
[백준 17244] 아맞다우산 (Java) (0) | 2021.06.10 |
[백준 1240] 노드사이의 거리 (Java) (0) | 2021.06.09 |
Comments