[백준] 1058 친구 JavaScript

혅·2024년 8월 14일

백준, 프로그래머스 -JavaScript-

목록 보기

132/215

문제

지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오.

A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다.

입력

첫째 줄에 사람의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 사람이 친구이면 Y, 아니면 N이 주어진다.

출력

첫째 줄에 가장 유명한 사람의 2-친구의 수를 출력한다.

예제 입력

5
NYNNN
YNYNN
NYNYN
NNYNY
NNNYN

예제 출력

내가 했던 풀이 방법

distance 배열을 N×N 크기의 Infinity로 채워진 배열로 초기화해준다. 해당 배열에는 사람 간의 거리를 의미하게 된다. Infinity인 경우, A의 친구의 친구의 .... 를 해도 연결되지 않는 친구라는 의미이다. 1인 경우에는 A와 B가 서로 친구라는 것을 의미하고, 2인 경우에는 A와 B는 친구가 아니지만, B와 C가 친구이고, A와 C가 친구라는 뜻이다.
입력받은 친구 정보를 통해 두 사람이 친구이면 1로 저장한다.
플로이드 워셜 방법을 이용해 모든 사람 간의 최단 거리를 찾을 것이다. 플로이드 워셜은 start에서 end까지 가는 거리와 start에서 mid를 거치고 end까지 가는 거리 중에 더 짧은 거리를 찾는 것이다. 그러므로 3중 for문을 이용한다. (플로이드 워셜은 효율성은 낮지만, 모든 노드 간의 최단 거리를 구할 때 자주 사용된다.) 이때, start와 end가 같은 경우는 무시한다.
플로이드 워셜로 최종 distance 배열에는 i와 j의 최단 거리가 담겨있다. 이를 for문을 이용해 i와 친구 거리가 2이하인 사람들의 수를 count에 저장해준다. count가 max보다 크다면, max 값을 count로 변경해준다. 이를 모든 사람에 대해 반복해주면 max에는 2-친구의 수가 제일 많은 사람의 친구 수가 저장되게 된다.

코드

const fs = require('fs');
let [N, ...friend] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

N = Number(N);

let distance = Array.from({ length: N }, () => Array(N).fill(Infinity));

for (let i = 0; i < N; i++) {
  friend[i] = friend[i].trim().split('');
  for (let j = 0; j < N; j++) {
    if (friend[i][j] === 'Y') distance[i][j] = 1;
  }
}

for (let mid = 0; mid < N; mid++) {
  for (let start = 0; start < N; start++) {
    for (let end = 0; end < N; end++) {
      if (start === end) continue;
      distance[start][end] = Math.min(distance[start][end], distance[start][mid] + distance[mid][end]);
    }
  }
}

let max = 0;
for (let i = 0; i < N; i++) {
  let count = 0;
  for (let j = 0; j < N; j++) {
    if (distance[i][j] <= 2) count++;
  }
  if (max < count) max = count;
}

console.log(max);