[구름톤 챌린지] 통신망 분석 (JS)

풀이 과정

1. 컴포넌트 연결 리스트 객체 생성
   이때 양방향으로 저장
2. 컴포넌트 번호를 값으로 가질 배열(visited) 생성
3. DFS로 각 컴포넌트에서 갈 수 있는 경로를 탐색하면서 visited 갱신, 통신 회선 +1
   이때 출발점만 visited 표시
   이때 통신 회선은 현재 컴포넌트 번호를 키, 회선 크기를 값으로 하는 객체를 만들고 갱신
4. 컴포넌트 마지막 번호 길이만큼의 배열 생성
5. visited의 컴포넌트 번호를 인덱스로 4번 배열에 추가
6. 5를 컴포넌트의 밀도 내림차순, 배열 길이 오름차순, 첫 번째 컴퓨터 번호 오름차순 정렬
7. 6번의 첫 번째 배열 정보 출력

코드

const readline = require('readline');
let rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let input = [];
let N, M;
rl.on('line', (line) => {
  input.push(line.split(' ').map(Number));
  [N, M] = input[0];
  if (input.length === M + 1) {
    rl.close();
  }
});

rl.on('close', () => {
  const obj = {};
  for (let i = 1; i <= M; ++i) {
    const [a, b] = input[i];
    if (!obj[a]) obj[a] = [];
    if (!obj[b]) obj[b] = [];
    obj[a].push(b);
    obj[b].push(a);
  }

  const visited = Array(N + 1).fill(0);
  const lengths = {};
  let num = 0;
  for (let i = 1; i <= N; ++i) {
    if (!obj[i] || visited[i]) continue;
    const q = [i];
    ++num;
    while (q.length) {
      const curr = q.pop();
      visited[curr] = num;
      if (!obj[curr]) continue;
      for (const next of obj[curr]) {
        if (visited[next]) continue;
        q.push(next);
        lengths[num] = (lengths[num] || 0) + 1;
      }
    }
  }

  const result = Array(num)
    .fill(0)
    .map((_, i) => [[i + 1], []]);
  for (let i = 1; i < visited.length; ++i) {
    if (visited[i] === 0) continue;
    result[visited[i] - 1][1].push(i);
  }
  const getDensity = ([num, arr]) => lengths[num] / arr.length;
  result.sort(
    (a, b) =>
      getDensity(b) - getDensity(a) ||
      a[1].length - b[1].length ||
      a[1][0] - b[1][0]
  );
  console.log(result[0][1].join(' '));
});

🤔

역시나 오늘도 실패... 그래도 종이에 그림 그려가면서 생각하다 보니 DFS 방식을 써서 풀어내긴 했다. 제출하면 케이스 반 정도가 통과 못하는데 그 이유는 모르겠다... 1시간 넘게 썼으니 패스~!

09/06 해설 참조 후 추가
해설을 보고서도 내가 왜 틀렸지 싶어서 조금씩 고쳐도 통과 못하는 케이스가 같았다. 주요 로직을 복붙해봤는데도 마찬가지였다. 설마 인풋 받는 게 이상한가 싶어서 거길 복붙해도 똑같고...
그래서 알아낸 건... 마지막에 process.exit()을 지웠더니 통과가 됐다.
테스트할 때 exit이 없으면 계속 켜져 있다가 시간 지나서 강제 종료되는 게 싫기도 하고, 처음 해설을 볼때 이런 코드가 있길래 계속 넣었었는데 이게 문제가 되다니 왜인지 모르겠지만 그래도 내 풀이가 틀리지 않았다는 사실에 기분이 나쁘지 않다.