[백준]2660번 회장뽑기

문제 이해하기

바로 직접적인 친구 → 1점 이라는 건가?

한 다리 걸쳐서 아는 친구가 있다면 → 2점이고

두 다리 걸쳐서 아는 친구 → 3점

세 다리 걸치면 → 4점

네 다리 걸치면 → 5점

• 이 때 , 만약 A - B 는 직접적인 친구이면서 A-C-B 이기도 하면 → A-B인 것으로 보는 거임. 즉 A→B까지 최소거리만을 취급하는 것.
• 회장은, 회원들 중, 점수가 가장 작은 사람.
• 구해야하는 것 : 회장의 점수 , 회장이 될 수 있는 모든 사람.

그래프처럼 사람들이 연결되어있다고 생각하고 ( 양방향그래프)

모든 edge는 가중치 1을 갖는다고 생각.

몇 사람을 통하면 “모두가 서로 알 수 있다” —> 그래프상 두 노드 사이에는 항상 경로가 존재한다.

모든 사람들이 다른 사람까지 “최소” 몇 사람을 거쳐야하는지 구해야한다.

• 모임에 속한 모든 사람들로부터 → 모임에 속한 모든 사람들로의 것을 구해야함 && 이 때 , 만약 A - B 는 직접적인 친구이면서 A-C-B 이기도 하면 → A-B인 것으로 보는 거임. 즉 A→B까지 최소거리만을 취급하는 것. ⇒ 플로이드 워셜 알고리즘을 사용
• 문제에서 N은 50이하임 → 플로이드 워셜 사용가능

문제 풀이

(:35)

어떤 사람의 모든 친구들 중, 한 명을 제외하고는 모두 직접적인 친구라하더라도 한 명이라도, 이 사람의 “친구의 친구” 라면 2점이 된다.

모든 사람에 대해, 이 사람의 "최대 점수"를 찾는다 ->이 최대점수가 min인 사람들이 회장 후보가 된다.

이를 구하면 된다.

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

public class Main {

    public static int n;
    public static int[][] dp = new int[50][50];
    public static final String EXIT = "-1 -1";

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;
    public static void setting() throws IOException{
        n = Integer.parseInt(br.readLine());
        // 초기화
        for(int i = 0 ; i<n;i++) {
            Arrays.fill(dp[i], 1000);
            dp[i][i] = 0;
        }
        int t1=0,t2=0;
        String temp = null;
        // 값을 받음
        while(true){
            temp = br.readLine();
            if(temp.equals(EXIT))break;
            st = new StringTokenizer(temp);
            t1 = convert2Int(st.nextToken())-1;
            t2 = convert2Int(st.nextToken())-1;
            dp[t1][t2]=1;
            dp[t2][t1]=1;
        }

    }
    public static int convert2Int(String str){
        return Integer.parseInt(str);
    }
    // 하나라도 "친구의 친구"이면 2점인거 아닌가? ㅇㅇ
    public static void solve(){
        int min = Integer.MAX_VALUE;
        int maxTemp = 0;
        ArrayList<Integer> candidate = new ArrayList<>(50);
        // 플로이드워샬
        for(int k = 0 ;k<n;k++){
            for(int a =0; a<n;a++){
                for(int b =0;b<n;b++){
                    if(a==b || a==k || b==k)continue;
                    // dp[a][b] 가 dp[a][k] 와 dp[k][b] 보다 크다면 업데이트
                    if(dp[a][b]>dp[a][k]+dp[k][b]) {
                        dp[a][b] = dp[a][k]+dp[k][b];
                    }

                }

            }
        }
        
        // 모든 사람에 대해, 이 사람의 "최대 점수"를 찾는다 -> min인 사람들이 회장 후보가 된다.
        for(int a =0; a<n;a++){
            maxTemp = 0;
            for(int b = 0 ; b<n;b++){
                if(dp[a][b]>maxTemp)maxTemp = dp[a][b];
            }
            if(min == maxTemp)candidate.add(a);
            else if(min > maxTemp){
                candidate.clear();
                min = maxTemp;
                candidate.add(a);
            }
        }
        // 회장인 사람의 점수, 회장후보의 인원 출력
        System.out.println(new StringBuilder("").append(min).append(" ").append(candidate.size()));
        // 회장 후보들의 번호를 오름차순으로 출력
        StringBuilder sb = new StringBuilder("");
        for (Integer integer : candidate) {
            sb.append((integer+1)).append(" ");
        }
        System.out.println(sb);
    }
    public static void main(String[] args)throws IOException {
        setting();
        solve();
    }
}