[BOJ] 1389 케빈 베이컨의 6단계 법칙

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

친구 관계를 주고, 케빈 베이컨의 숫자가 가장 작은 사람을 찾는 문제이다.

Python

from collections import deque

N, M = map(int, input().split())

adj = [[] for _ in range(N)]
kevin = []

for _ in range(M):
  a, b = map(lambda x: x-1,map(int, input().split()))
  adj[a].append(b)
  adj[b].append(a)
  
ans = (-1, 987654231) 

def bfs(start, goal):
  chk = [False] * N
  chk[start] = True
  dq = deque()
  dq.append((start, 0))
  while dq:
    now, d = dq.popleft()
    if now == goal:
      return d
    
    nd = d+1
    for nxt in adj[now]:
      if not chk[nxt]:
        chk[nxt] = True
        dq.append((nxt, nd))


def get_kevin(start):
  tot = 0

  for i in range(N):
    if i!= start:
      tot += bfs(start, i)

  return tot

for i in range(N):
  kevin.append(get_kevin(i))


print(kevin)

for i, v in enumerate(kevin):
  if ans[1] > v:
    ans = (i, v)

print(ans[0]+1)

모든 점에 대해서 BFS 돌면서 거리를 구했고, kevin이라는 리스트에 각 사람별로 거리합이 얼만큼 되는지 저장했다. 그리고 가장 작은 합을 가진 사람의 index를 뽑아서 출력했다.

Javascript

1차 실패

const input = require("fs").readFileSync(process.platform === "linux" ?
  "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((el) => el.split(" ").map(Number));

const [n, m] = input[0];

const bacon = Array.from({ length: (n + 1) }, () => Array(n + 1).fill(0));
const adj = Array.from({ length: (n + 1) }, () => Array(0));

for (let i = 1; i <= m; i++) {
  const [a, b] = input[i];
  adj[a].push(b);
  adj[b].push(a);
}

for (let i = 1; i < n + 1; i++) {
  const que = [[i, 0]]
  let idx = 0;

  const visited = Array(n + 1).fill(true);
  visited[i] = false;

  while (idx < que.length) {
    [now, count] = que[idx++];
    adj[now].forEach((next) => {
      if (visited[next]) {
        visited[next] = false;
        que.push([next, count + 1])
        if (bacon[now][next] == 0 || bacon[now][next] > count + 1) {
          bacon[i][next] = count + 1;
          bacon[next][i] = count + 1;
        }
      }
    });
  }
}

let ans = 3000 * n;
let b = 0;
for (i = 1; i <= n; i++) {
  const tmp = bacon[i].reduce((prev, curr) => prev + curr, 0);
  if (ans > tmp) {
    ans = tmp;
    b = i;
  }
}

console.log(b)

파이썬과는 조금 다르게 전체 BFS를 돌면서 bacon이라는 2차원 배열에 i부터 다른 점까지의 거리를 저장했고, 마지막에 그 합을 구해서 가장 작은 index를 구했다. 그런데 3%에서 실패했다.

2차

const input = require("fs").readFileSync(process.platform === "linux" ?
  "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((el) => el.split(" ").map(Number));

const [n, m] = input[0];

const bacon = Array.from({ length: (n + 1) }, () => Array(n + 1).fill(0));
const adj = Array.from({ length: (n + 1) }, () => Array(0));

for (let i = 1; i <= m; i++) {
  const [a, b] = input[i];
  adj[a].push(b);
  adj[b].push(a);
}

const ans = [0, 3000 * n * m];

for (let i = 1; i < n + 1; i++) {
  const que = [[i, 0]]
  let idx = 0;

  const visited = Array(n + 1).fill(true);
  visited[i] = false;
  let tmp = 0;

  while (idx < que.length) {
    [now, count] = que[idx++];
    adj[now].forEach((next) => {
      if (visited[next]) {
        visited[next] = false;
        que.push([next, count + 1])
        tmp += count + 1;
      }
    });
  }

  if (ans[1] > tmp) {
    ans[0] = i;
    ans[1] = tmp;
  }
}


console.log(ans[0])

조금 수정해서 i별로 count의 합을 구했고 매번 ans와 비교해서 가장 작은 i와 베이컨 수를 저장했다.
이렇게 하니까 통과할 수 있었다.

추측으로는 첫 번째 방법에서는 다른 점을 탐색하면서 거리구한 값이 훼손되어서 그런 것 같다.