[JS][백준]회장뽑기

문제 번호

2660번: 회장뽑기

 

 

 

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 플로이드–워셜

 

문제 풀이

 플로이드 워셜 알고리즘을 사용해서 문제를 풀었다.

플로이드 워셜 알고리즘을 사용해서 각 회원별로 다른 모든 친구까지 몇 다리를 건너서 친구가 될 수 있는지를 조사하면된다.

 

 그 후에 각 회원들별로 가장 많은 친구를 건너서 알 수 있는 친구가 있을때, 이 친구와 몇명의 친구를 통해서 알 수 있는지 찾아보면된다. 예를들어 3번회원이 다른 회원들과 [1, 2, 3, 3, 2, 1] 만큼의 친구들을 건너야 알 수 있다고 했을때 3번 회원의 가장 많은 친구를 건너서 알 수 있는 친구의 수 는 3이 된다.

 

전체 코드

/**
 * 플로이드 와샬로 모든 점에서 모든 점까지 거리를 구한다.
 * 이때 i번째 점에서 다른점까지의 최대 거리가 가장 max라 하면 이 값이 가장 작은 i점을 찾는다.
 */
function main() {
  let answer = '';
  const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
  const N = +input[0];
  let f = input.slice(1).map(_ => _.trim().split(' ').map(Number));

  let arr = new Array(N).fill(null).map(_ => new Array(N).fill(Infinity));
  
  for (let i = 0; i < f.length; i++) {
    let [a, b] = f[i];
    if (a === -1 && b === -1)
      break;
    arr[a-1][b-1] = 1;
    arr[b-1][a-1] = 1;
  }
  
  answer = sol(arr, N);

  return console.log(answer.trim());
}
function sol(arr, N) {
  let answer = '';

  let chairManScore = 0;
  let numOfCandidate = 0;
  let candidate = [];

  for (let k = 0; k < N; k++) { // 경유
    for (let i = 0; i < N; i++) {  // 출
      for (let j = 0; j < N; j++) {  // 도
        if (arr[i][k] + arr[k][j] < arr[i][j])
          arr[i][j] = arr[i][k] + arr[k][j];
      }
    }
  }    
  for(let i=0; i<N; i++){
    arr[i][i] = 0;
  }

  // 점수가 가장 낮은 회원을 찾는다.
  let min = Infinity
  for(let i=0; i<N; i++) {
    let closer = Math.max(...arr[i]);
    if(closer < min)
      min = closer;
  }
  chairManScore = min;

  // 회장이 될 사람을 찾는다.
  for(let i=0; i<N; i++) {
    let tempMax = Math.max(...arr[i]);
    if(tempMax === chairManScore) {
      numOfCandidate++;
      candidate.push(i+1);
    }
  }

  answer += chairManScore + ' ' + numOfCandidate + '\n';
  answer += candidate.join(' ')
  
  return answer;
}
main();

특이사항