[JAVA] 백준 2660번 【G5.회장뽑기】

문제

2660번: 회장뽑기

 

 

풀이

1️⃣ 플로이드 알고리즘 사용

💡 떠오른 Idea

처음에 문제가

'어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.'

라고 나와있어서 이해하기가 힘들었었다.

근데, 이 문제를 직관적으로 이해해보니

'특정 회원이 있을 때 가장 사이가 먼 회원은 몇명을 거쳐서 가야하는가'

로 해석하면 됨을 알 수 있었다.

따라서, 플로이드 알고리즘을 통해 특정 회원이 다른 회원에 도달하는 비용을 플로이드 알고리즘을 이용하여 구하고

각 회원 별 최대 비용을 구한 뒤, 그 비용의 최솟값을 구하고 해당 최솟값을 갖는 회원들을 모두 구하면 끝이 날 것 이다.

 

public class Main {

    public static void main(String[] args) throws IOException {
        final int MAX = 100;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[][] graph = new int[N][N];

        // 자기 자신으로 가는 경로 외에 최대값으로 변환
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (r == c) {
                    graph[r][c] = 0;
                } else {
                    graph[r][c] = MAX;
                }
            }
        }


        // 가장 가까운 사이는 1로 먼저 입력해줌
        while (true) {
            String[] input = br.readLine().split(" ");
            if (input[0].equals("-1")) {
                break;
            }

            int u = Integer.parseInt(input[0] )- 1;
            int v = Integer.parseInt(input[1]) - 1;
            graph[u][v] = 1;
            graph[v][u] = 1;
        }

        // 플로이드 알고리즘 적용
        for (int m = 0; m < N; m++) {
            for (int u = 0; u < N; u++) {
                for (int v = 0; v < N; v++) {
                    graph[u][v] = Math.min(graph[u][v], graph[u][m] + graph[m][v]);
                }
            }
        }


        // 맵에 점수 별 회원들을 기록
        Map<Integer, List<Integer>> scores = new HashMap<>();
        int minScore = MAX;

        for (int r = 0; r < N; r++) {
            int maxScoreByMember = Arrays.stream(graph[r]).max().getAsInt();
            minScore = Math.min(minScore, maxScoreByMember);
            if (scores.containsKey(maxScoreByMember)) {
                scores.get(maxScoreByMember).add(r + 1);
            } else {
                List<Integer> members = new ArrayList<>();
                members.add(r + 1);
                scores.put(maxScoreByMember, members);
            }
        }

        List<Integer> members = scores.get(minScore);

        StringBuilder sb = new StringBuilder();
        sb.append(minScore + " " + members.size() + "\n");
        for (int member : members) {
            sb.append(member + " ");
        }

        System.out.println(sb);

    }
}

 

결과

 

마지막에 데이터를 처리하는 과정을 제외하면 플로이드 알고리즘을 사용하면 쉽게 해결할 수 있는 문제였다.