[Javascript] 프로그래머스 - 네트워크

문제 설명

네트워크는 컴퓨터들이 서로 직접 또는 간접적으로 연결되어 정보를 교환할 수 있는 집합을 의미합니다. 주어진 n개의 컴퓨터와 연결 정보가 담긴 computers 배열을 이용하여 서로 연결된 네트워크의 개수를 구하는 문제입니다.

제한 사항

• n은 1 이상 200 이하의 자연수입니다.
• 각 컴퓨터는 0부터 n-1까지의 정수로 표현됩니다.
• computers[i][j]가 1이면 i번 컴퓨터와 j번 컴퓨터가 연결된 것입니다.
• computers[i][i]는 항상 1입니다.

해결 방법

알고리즘: DFS(깊이 우선 탐색)

1. 방문 여부를 체크하는 visit 배열을 생성합니다.
2. 각 컴퓨터를 순회하면서 방문하지 않은 경우 DFS를 수행합니다.
3. DFS를 통해 하나의 네트워크를 탐색하면 네트워크 개수를 증가시킵니다.
4. 모든 컴퓨터를 순회한 후 네트워크 개수를 반환합니다.

시간 복잡도

• 각 노드(컴퓨터)에 대해 DFS 탐색을 수행하므로 O(n²) 의 시간 복잡도를 가집니다.

구현 코드

function solution(n, computers) {
  let answer = 0;
  let visit = new Array(n).fill(false);

  function dfs(index) {
    for (let i = 0; i < n; ++i) {
      if (computers[index][i] === 1 && !visit[i]) {
        visit[i] = true;
        dfs(i);
      }
    }
  }

  for (let i = 0; i < n; ++i) {
    if (visit[i]) {
      continue;
    }

    visit[i] = true;
    dfs(i);
    ++answer;
  }

  return answer;
}