[백준]2660: 회장뽑기 - JAVA

[백준]2660: 회장뽑기

www.acmicpc.net/problem/2660

2660번: 회장뽑기

풀이

모든 회원 간의 관계를 조사한 다음에 그 중에 최대값을 찾아 회원 점수를 찾아낸 뒤, 그 중 최소값은 갖는 후보가 회장 후보가 된다.

 

즉, 모든 회원간의 관계(거리)를 알아야 하므로 플로이드-와샬 알고리즘을 사용하였다. 

friend[i][j]보다 friend[i][k] + friend[k][j]가 더 작다면(k를 경유하여 가는 거리가 더 작다면) 갱신해준다.

 

이렇게 구한 모든 회원의 관계 중에서 각 회원의 점수를 구하려면 각 회원의 1번째 인덱스의 최대값을 구해주면 된다. 그리고 그 중의 최소값이 회장 후보의 점수가 될 것이다.

 

arraylist를 사용하여 최소값과 일치하는 후보가 있다면 담아주고 list의 크기와 요소를 사용하여 출력해주었다. 

 

이 문제에서는 회원수가 최대 50명으로 제한되어 있으므로 max값은 50 * 50보다 큰 값중 하나를 적절히 선택해 주면 된다. (이때 플로이드-와샬 연산에서 friend[i][k] + friend[k][j]가 있으므로 둘다 매우 큰 값일 때 int범위를 벗어나 음수가 될 수 있으므로 이점 유의하여 적절하게 큰 값을 선택해 주어야 한다.)

 

코드

import java.util.*;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        int max = 251;
        
        int[][] friend = new int[n + 1][n + 1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                friend[i][j] = max;
            }
        }
        
        while(true) {
            int n1 = scan.nextInt();
            int n2 = scan.nextInt();
            if(n1 == -1 && n2 == -1) break;
            friend[n1][n2] = 1;
            friend[n2][n1] = 1;
        }
        
        for(int k = 1; k <= n; k++) {
            friend[k][k] = 1;
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    if(friend[i][j] > friend[i][k] + friend[k][j]) {
                        friend[i][j] = friend[i][k] + friend[k][j];
                    }
                }
            }
        }
        
        int[] scores = new int[n + 1];
        int min = Integer.MAX_VALUE; //회장 점수 
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                scores[i] = Math.max(scores[i], friend[i][j]);
            }
            min = Math.min(min, scores[i]);
        }
        
        ArrayList<Integer> list = new ArrayList<>(); //회장 후보 목록
        for(int i = 1; i <= n; i++) {
            if(scores[i] == min) list.add(i);
        }
        
        System.out.println(min + " " + list.size());
        for(int temp : list) {
            System.out.print(temp + " ");
        }
    }
}