[백준] 2660 회장찾기 (java)

1. 링크

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

2. 풀이

키워드: 플로이드 와샬

24. 플로이드 와샬(Floyd Warshall) 알고리즘

 

- 플로이드 와샬 알고리즘을 이용한다.

- 모든 정점 사이의 최단 거리를 구한다.

- 구한 최단 거리 중 큰 점수를 구한다.

- 큰 점수 중에서 가장 작은 점수(회장이 될 자격이있는) 를 구한 뒤 후보가 몇명이고 몇번째 인덱스가 후보인지를 출력한다.

3. 소스코드

- 좀 지저분하게 풀었지만.. 맞았다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

/**
 * https://www.acmicpc.net/problem/2660
 */
public class BG_회장뽑기 {

  static final int INF = 987654321;

  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][N];

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

    while (true) {
      String[] s = br.readLine().split(" ");
      int x = Integer.parseInt(s[0]) - 1;
      int y = Integer.parseInt(s[1]) - 1;

      if (x + 1 == -1 && y + 1 == -1) {
        break;
      }

      arr[x][y] = 1;
      arr[y][x] = 1;
    }

    for (int k = 0; k < N; k++) {
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          if (arr[i][k] + arr[k][j] < arr[i][j]) {
            arr[i][j] = arr[i][k] + arr[k][j];
          }
        }
      }
    }

    int score = 0;
    int[] scores = new int[N]; // 친구 점수 목록
    int resultScore = INF;

    // 첫째줄: 회장 후보의 점수와 후보의 수 출력
    // 둘째줄: 회장 후보를 오름차순으로 출력
    for (int i = 0; i < N; i++) {
      score = 0;
      for (int j = 0; j < N; j++) {
        if (arr[i][j] != INF && arr[i][j] > score) {
          score = arr[i][j]; // 가장 큰 점수를 기록
        }
      }

      scores[i] = score;
      if (resultScore > score) {
        resultScore = score; // 가장 작은 회장 후보 점수로 갱신
      }
    }

    int cnt = 0;
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < N; i++) {
      if (scores[i] == resultScore) {
        cnt++;
      }
    }

    sb.append(resultScore).append(" ").append(cnt);
    sb.append("\n");

    for (int i = 0; i < N; i++) {
      if (scores[i] == resultScore) {
        sb.append(i + 1).append(" ");
      }
    }

    bw.write(sb.toString());
    bw.flush();
    br.close();
    bw.close();
  }

}