[JAVA] BOJ 백준 2660번 - 회장뽑기

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

---

2. 내가 푼 방법

플로이드 와샬 알고리즘을 이용해 정점 v1과 v2 사이의 가중치를 구해줬다.

정점 v1에서 v2로 가는 최소 비용  vs  정점 v1에서 정점 x로 가는 비용 + 정점 x에서 정점 v2로 가는 비용

을 비교해 주면서 최소 가중치를 구할 수 있게 된다.

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;
            if (arr[i][k] == 0 || arr[k][j] == 0) continue;

            if (arr[i][j] == 0 || arr[i][j] > arr[i][k] + arr[k][j]) {
                 arr[i][j] = arr[i][k] + arr[k][j];
            }
        }
    }
}

 

이제 가중치가 작을수록 회장 후보에 들게 되기 때문에, 한 사람이 다른 사람과 맺고 있는 최대 가중치를 확인해야 한다.

TreeMap을 이용해 key는 가중치를, value는 회원 번호를 리스트로 넣어주었다.

TreeMap<Integer, List<Integer>> map = new TreeMap<>();

for (int i = 1; i <= N; i++) {
    int score = 0;

    for (int j = 1; j <= N; j++) {
        score = Math.max(score, arr[i][j]);
    }

    List<Integer> tmp = new ArrayList<>();
    if (map.containsKey(score)) tmp = map.get(score);

    tmp.add(i);
    map.put(score, tmp);
}

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B2660.java

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

class Main {
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N+1][N+1];


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

            if (v1 == -1 && v2 == -1) break;

            arr[v1][v2] = 1;
            arr[v2][v1] = 1;
        }

        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;
                    if (arr[i][k] == 0 || arr[k][j] == 0) continue;

                    if (arr[i][j] == 0 || arr[i][j] > arr[i][k] + arr[k][j]) {
                        arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }
            }
        }

        TreeMap<Integer, List<Integer>> map = new TreeMap<>();

        for (int i = 1; i <= N; i++) {
            int score = 0;

            for (int j = 1; j <= N; j++) {
                score = Math.max(score, arr[i][j]);
            }

            List<Integer> tmp = new ArrayList<>();
            if (map.containsKey(score)) tmp = map.get(score);

            tmp.add(i);
            map.put(score, tmp);
        }

        bw.write(map.firstKey()+" ");
        bw.write(map.get(map.firstKey()).size()+"\n");

        for (Integer i : map.get(map.firstKey())) {
            bw.write(i+" ");
        }

        br.close();
        bw.flush();
        bw.close();
    }
}

---

4. 결과 및 회고

플로이드 와샬이라는 새로운 알고리즘에 대해 알게 되었다.

이 알고리즘을 응용해서 풀어야 하는 다른 문제들도 풀어봐야겠다.