[BOJ2660] 회장뽑기 (플로이드 워셜, 최단거리)

 

 

---

문제 링크

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

2660번: 회장뽑기

 

문제 풀이

1) 각 노드별로 다른 노드에 대한 최단 거리를 구한다 (양방향 관계, 플로이드 워셜 알고리즘 사용)

- 이때 시간복잡도 O(N^3)

2) 각 노드별 최단 거리를 구한 후 그 중 최대값이, 해당 노드의 회장 점수가 된다

3) 회장 점수가 최소가 되는 번호를 구해서 출력한다

 

 

문제에서 아래 부분이 조금 이해가 안 되었는데 결론은 각 노드별 최단 거리를 구해라는 의미였다

각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구사이이면서 동시에 친구의 친구사이이면, 이 두사람은 친구사이라고 본다.

1 -> 2 , 1 -> 3, 3 -> 2  이런 관계라면  1 -> 2 가 (친구 사이)이면서 , 1 -> 3 -> 2 (친구의 친구 사이)이면, 1과 2는 친구사이라 함

1	2	3
0	1	1

 

 

 

제출 코드

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int N;
    static int[][] floyd;
    static int INF = 51;
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        floyd = new int[N + 1][N + 1];
        for(int i = 1; i <= N; i++) {
            Arrays.fill(floyd[i], INF);

            floyd[i][i] = 0;
        }

        String line;
        while(!"-1 -1".equals(line = br.readLine())) {
            st = new StringTokenizer(line);

            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            floyd[from][to] = 1;
            floyd[to][from] = 1;
        }
    }

    static void pro() {
        for(int k = 1; k <= N; k++) {
            for(int i = 1; i <= N; i++) {
                for(int j = 1; j <= N; j++) {
                    if(i == j) continue;

                    floyd[i][j] = Math.min(floyd[i][j], floyd[i][k] + floyd[k][j]);
                }
            }
        }

        Map<Integer, List<Integer>> resultMap = new HashMap<>();
        int result = INF;
        for(int i = 1; i <= N; i++) {
            int maxScore = 0;
            for(int j = 1; j <= N; j++) {
                maxScore = Math.max(maxScore, floyd[i][j]);
            }

            resultMap.putIfAbsent(maxScore, new ArrayList<>());
            resultMap.get(maxScore).add(i);
            result = Math.min(result, maxScore);
        }


        sb.append(result).append(" ").append(resultMap.get(result).size()).append("\n");
        List<Integer> list = resultMap.get(result);
        for(int i : list) sb.append(i).append(" ");

        System.out.println(sb);

    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}