[JAVA]백준_2660_회장뽑기

문제링크

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

2660번: 회장뽑기

 

 

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_2660 {
//    예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다.
//    어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다.
//    또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.
//            4점, 5점 등은 같은 방법으로 정해진다. 각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구사이이면서 동시에 친구의 친구사이이면,
//            이 두사람은 친구사이라고 본다.
//  회장은 회원들 중에서 점수가 가장 작은 사람이 된다. 회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 프로그램을 작성하시오.
    static int INF = 999999999;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); //회원의 수
        int map[][] = new int[N+1][N+1];

        for(int i=0;i<=N;i++){
            for(int j=0;j<=N;j++)
                if(i!=j) map[i][j] = INF;
        }

        while(true){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if(a==-1 && b==-1) break;

            map[a][b] = 1;
            map[b][a] = 1;
        }

        for(int k=1;k<=N;k++){
            for(int i=1;i<=N;i++){
                for(int j=1;j<=N;j++){
                    map[i][j] = Math.min(map[i][j],map[i][k]+map[k][j]);
                }
            }
        }

        //for(int i=1;i<=N;i++) System.out.println(Arrays.toString(map[i]));

        for(int i=1;i<=N;i++){
            int sum = 0;
            for(int j=1;j<=N;j++){
                sum +=map[i][j];
            }
            map[i][0] = sum;
        }

        //for(int i=1;i<=N;i++) System.out.println(Arrays.toString(map[i]));
        int min = Integer.MAX_VALUE;
        int score = 0;
        int cnt = 0;
        for(int i=1;i<=N;i++){
            //map[i][0]
            if(map[i][0]<min){
                min = map[i][0];
                score = 0;
                for(int j=1;j<=N;j++) score = Math.max(score,map[i][j]);
                cnt=0;
                cnt++;
            }
            else if(map[i][0] == min){
                min = map[i][0];
                cnt++;
            }
        }

        System.out.println(score+" "+cnt);
        for(int i=1;i<=N;i++){
            if(map[i][0] ==min) System.out.print(i+" ");
        }
    }
}