Programmers / Level 3 / 네트워크 / JS

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

풀이

function solution(n, computers) {
  const visited = Array.from({ length: n }, () => false);
  let network = 0;

  for (let i = 0; i < n; i++) {
    // 아직 방문하지 않았다면 dfs로 네트워크를 탐색한다.
    if (!visited[i]) {
      dfs(i);
      network++;
    }
  }

  function dfs(cur) {
    for (let i = 0; i < n; i++) {
      if (visited[i]) {
        continue;
      }
      // 이어져 있지 않다면 건너뛴다.
      if (computers[cur][i] === 0) {
        continue;
      }

      visited[i] = true;
      dfs(i);
    }
  }

  return network;
}

 

문제는 간단히 말하면 이어져있는 그룹이 몇개인지 세는 문제이다.

Level3 이라기엔 상당히 쉬운 문제이다.

 

dfs로 현재의 컴퓨터와 이어져 있는 컴퓨터는 모두 방문처리를 한다.

따라서 dfs를 마치면 하나의 네트워크가 형성되게 된다.

 

아직 네트워크가 형성되지 않은 컴퓨터는 방문처리가 되어있지 않았을 것이기 때문에,

방문처리 되어있지 않은 컴퓨터에서 다시 dfs를 이용해 네트워크를 형성해주면 된다.