프로그래머스 - 네트워크 (JavaScript)

생각해보기

인접 리스트로만 풀다보니 인접 행렬에 대해 미숙했다.

인접 리스트와 인접 행렬에 대한 구현과 탐색을 다시 숙지하자.

 

• 네트워크의 개수 = 부분 그래프의 개수
• 임의의 정점 x에 대해 BFS 또는 DFS로 탐색하였을 때, 방문하지 않은 노드들은 임의의 정점 x와 같은 그래프에 속해 있지 않다.
• 따라서 방문하지 않은 노드들에 대해 BFS 또는 DFS 탐색을 다시 수행한다.
• 조건문 안에서 BFS 또는 DFS 함수가 호출된 횟수가 곧 네트워크의 개수이다.

 

풀이)

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

  // BFS
  function bfs(x) {
    let queue = [x];
    visited[x] = true;

    while (queue.length) {
      let c = queue.shift();
      for (let i = 0; i < n; i++) {
        if (visited[i] == false && computers[c][i] == 1) {
          visited[i] = true;
          queue.push(i);
        }
      }
    }
  }
  for (let j = 0; j < n; j++) {
    if (visited[j] == false) {
      bfs(j);
      answer += 1;
    }
  }

  return answer;
}

// DFS - Recursion
function solution(n, computers) {
  let answer = 0;
  let visited = Array.from({ length: n }, () => false);

  function dfs(x) {
    visited[x] = true;

    for (let i = 0; i < n; i++) {
      if ((visited[i] == false) & (computers[x][i] == 1)) {
        dfs(i);
      }
    }
  }

  for (let j = 0; j < n; j++) {
    if (visited[j] == false) {
      dfs(j);
      answer += 1;
    }
  }

  return answer;
}

// DFS - Stack
function solution(n, computers) {
  let answer = 0;
  let visited = Array.from({ length: n }, () => false);

  function dfs(x) {
    let stack = [x];
    visited[x] = true;

    while (stack.length) {
      k = stack.pop();
      for (let i = 0; i < n; i++) {
        if (visited[i] == false && computers[k][i] == 1) {
          visited[i] = true;
          stack.push(i);
        }
      }
    }
  }

  for (let j = 0; j < n; j++) {
    if (visited[j] == false) {
      dfs(j);
      answer += 1;
    }
  }

  return answer;
}