[JavaScript] 구름톤 챌린지 4주차 코딩테스트 : 통신망 분석 (다시 풀어야 함)

📌  문제

📌  입력

📌  출력 및 예제

---

📌  풀이

알아야 하는 것

• DFS

구할 것

• 그래프 구현까지는 괜찮은데 DFS 부분부터 좀 까다로워졌다...
• 특히 출력할 때 조건이 3가지인데 이걸 다 고려해서 코드를 짜야 하는 부분이 좀 어려웠다.
• 다른 분들 풀이를 참고하고 짬뽕한 거라 아직 로직이 100% 이해가 안 간다. 다시 풀어봐야함.

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let N, M;
let graph = [];

// 그래프 구성
rl.on('line', (line) => {
  // 첫 번째 줄에서 N을 읽어올 경우
  if (!N) {
    [N, M] = line.split(" ").map(Number);
    graph = new Array(N + 1).fill().map(() => []);

    // N이 초기화된 후 받는 입력값
  } else {
    const [start, end] = line.split(" ").map(Number);
    graph[start].push(end);
    graph[end].push(start);
  }
});

rl.on('close', () => {
  solution(N, M, graph);
});

// visited에서 방문 정점 체크 && history에서 방문 순서 체크
function dfs(start, visited, graph) {
  const stack = [start];
  visited[start] = true;
  const history = [];

  while (stack.length > 0) {
    const cur = stack.pop();
    history.push(cur);

    for (const next of graph[cur]) {
      if (!visited[next]) {
        stack.push(next);
        visited[next] = true;
      }
      // 방문한 간선 삭제 (이 부분은 필요하지 않을 수 있음)
      graph[next] = graph[next].filter((node) => node !== cur);
    }
  }
  return history;
}

function solution(N, M, graph) {
  let answerHistory = [];
  let maxDensity = 0;
  const visited = Array(N + 1).fill(false);

  for (let start = 1; start <= N; start++) {
    if (!visited[start]) {
      const history = dfs(start, visited, graph);
      let edges = 0;

      // 통신 회선 개수
      for (const i of history) {
        edges += graph[i].length;
      }

      // 밀도 계산 (통신 회선 / 컴퓨터 개수)
      const density = edges / history.length;

      // 1번 조건
      if (maxDensity < density) {
        maxDensity = density;
        answerHistory = history;
        // 2번 조건
      } else if (maxDensity === density) {
        if (answerHistory.length > history.length) {
          maxDensity = density;
          answerHistory = history;
          // 3번 조건
        } else if (answerHistory.length === history.length) {
          if (Math.min(...answerHistory) > Math.min(...history)) {
            maxDensity = density;
            answerHistory = history;
          }
        }
      }
    }
  }

  console.log(answerHistory.sort((a, b) => a - b).join(' '));
}