[백준] 2660. 회장뽑기 풀이 (Python, JavaScript)

2660번: 회장뽑기

접근한 방법

플로이드 워셜로 최단 경로를 구해 갱신하는 방법으로 접근합니다. 플로이드 워셜은 n^3 복잡도까지 커버할 수 있어서 표본 수가 적다면 가장 쉽고 간단하게 풀이할 수 있습니다. 

 

각 정점을 순회하면서 중간 지점을 통해 경로하는 거리와 원래 놓여있는 거리 중 더 짧은 것으로 결정합니다. 최대한 중간지점을 통해 가지 않는 것이 거리가 1로 가장 짧으므로 회장 후보로 등록될 가능성이 클 것입니다.

 

탐색 후 각 정점마다 입력되어 있는 거리중 가장 먼 거리를 최종 거리로 입력한 후 그 중 가장 짧은 거리를 가진 지점이 회장 후보가 됩니다.

 

Python

import sys
input = sys.stdin.readline

n = int(input())
arr = [[n] * n for _ in range(n)]
dist = [0] * n # 각 정점별 가장 먼 거리에 대한 거리 표
for i in range(n):
    for j in range(n):
        if i == j:
            arr[i][j] = 0
while 1:
    a, b = map(int, input().split())
    if [a, b] == [-1, -1]:
        break
    arr[a - 1][b - 1], arr[b - 1][a - 1] = 1, 1

for k in range(n): # k : 중간지점
    for i in range(n):
        for j in range(n):
            # 중간 지점을 통해 이동하는 거리가 더 짧으면 갱신
            arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j])
for i in range(n):
    # 각 정점별로 가장 먼 거리를 입력
    dist[i] = max(arr[i])

t = min(dist) 
print(t, dist.count(t))
[print(i + 1, end=" ") if dist[i] == t else None for i in range(n)]

 

JavaScript

function solution(n, edges) {
  const arr = Array.from({ length: n }, () => Array(n).fill(n));
  const dist = Array(n).fill(0);
  for (let i = 0; i < n; i += 1) {
    for (let j = 0; j < n; j += 1) {
      if (i === j) arr[i][j] = 0;
    }
  }
  edges.forEach((edge) => {
    const [a, b] = edge;
    arr[a - 1][b - 1] = 1;
    arr[b - 1][a - 1] = 1;
  });
  for (let k = 0; k < n; k += 1) {
    for (let i = 0; i < n; i += 1) {
      for (let j = 0; j < n; j += 1) {
        arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
      }
    }
  }
  for (let i = 0; i < n; i += 1) dist[i] = Math.max(...arr[i]);
  const t = Math.min(...dist);
  const result = [[t, 0], []];
  for (let i = 0; i < n; i += 1) {
    if (dist[i] == t) {
      result[0][1] += 1;
      result[1].push(i + 1);
    }
  }
  return result;
}
console.log(
  solution(5, [
    [1, 2],
    [2, 3],
    [3, 4],
    [4, 5],
    [2, 4],
    [5, 3],
  ])
);