[JavaScript] 프로그래머스 코딩테스트 레벨 3 : 네트워크

📌  문제

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

📌  제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

📌  입출력 예

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

---

📌  풀이

구할 것

• 직접적으로 연결된 것을 타고 간접적으로도 연결 되어 있는지 확인해야 하는 문제로 dfs, bfs 모두 가능하다.
• 기본적인 구성은 방문 여부를 확인할 배열 visited를 기준으로, 컴퓨터별로 방문을 확인하되 각 컴퓨터가 연결되었는지(1이면서 방문하지 않았는지) 확인하는 것이다.

1. dfs

• 방문 확인 배열 visited를 선언하고 정답을 반환할 answer를 0으로 초기화한다. 컴퓨터 개수만큼 순회하면서 방문하지 않았을 경우에 dfs를 실행 시킨다. dfs가 종료되면 (깊게 내려간 모든 탐색) 네트워크의 개수를 알 수 있으므로 1을 더해준다.
• dfs를 실행하게 되면 해당 컴퓨터는 방문한 것으로 변경해준다. 그 컴퓨터를 기준으로 연결된 컴퓨터들을 확인할 때, 연결이 되어야 하니 1이어야 하면서 아직 방문하지 않았다면 재귀함수로 다시 dfs를 실행 시킨다. 이 때 종료 조건은 1이 아니거나 모두 방문한 경우다.
• 예컨대 1번 컴퓨터부터 순회를 시작할 때 visited[0]은 true가 된다. 1번 컴퓨터는 [1, 1, 0]이므로 1은 if문에서 두 번째 조건에 부합하지 않아 넘어간다. 다음 1은 1번째 인덱스로 visited[1] === false이므로 if문 조건에 해당해 재귀함수를 시작하게 된다. 2번 컴퓨터를 기준으로 시작할 때 [1, 1, 0]에서 1, 1은 모두 true가 되었으니 2번째 인덱스로 가지만 값이 0이므로 재귀함수를 종료하게 된다. 이 때 answer ++가 된다. 즉 1번-2번 컴퓨터가 연결되어 함께 진행됐다. 다음 3번 컴퓨터가 true가 되고 탐색하지만, if문의 첫 번째 조건에는 맞지만 두 번째 조건(방문하지 않아야 함 === 자기 자신이 아니어야 함)에 부합하지 않아 종료되고 answer ++가 되어 최종 2가 리턴된다. 

function dfs(computers, visited, node) {
  // dfs 진행하면서 방문으로 변경
  visited[node] = true;

  // 컴퓨터별 연결된 네트워크 탐색
  // 연결 되어 있고 방문하지 않았다면 그 컴퓨터로 다시 내려감
  for (let i = 0; i < computers[node].length; i++) {
    if (computers[node][i] === 1 && !visited[i]) {
      dfs(computers, visited, i);
    }
  }
}

function solution(n, computers) {
  // 방문 확인
  const visited = Array(n).fill(false);
  let answer = 0;

  // 컴퓨터 개수만큼 순회하면서 방문하지 않았을 경우 dfs
  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      dfs(computers, visited, i);
      answer++;
    }
  }
  return answer;
}

 

2. bfs

• dfs와 기본 구성은 동일하며 구현 시 queue로 구현한다. 대신 여기는 재귀로 내려가는 것 대신 queue에 넣어주고 방문 표시를 하는 점이 다르다.

function bfs(computers, visited, node) {
  const queue = [];
  queue.push(node);

  while (queue.length > 0) {
    const currentNode = queue.shift();

    for (let i = 0; i < computers[currentNode].length; i++) {
      if (computers[currentNode][i] === 1 && !visited[i]) {
        queue.push(i);
        visited[i] = true;
      }
    }
  }
}

function solution(n, computers) {
  // 방문 확인
  const visited = Array(n).fill(false);
  let answer = 0;

  // 컴퓨터 개수만큼 순회하면서 방문하지 않았을 경우 dfs
  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      bfs(computers, visited, i);
      answer++;
    }
  }
  return answer;
}