[프로그래머스] [DFS] Lv.3 네트워크 JavaScript

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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

입출력 예 설명

예제 #1

아래와 같이 2개의 네트워크가 있습니다.

예제 #2

아래와 같이 1개의 네트워크가 있습니다.

---

문제풀이

💡 문제풀이 과정

• DFS로 풀이. 방문 체크를 위한 visited 배열을 만들고 각 노드간 방문 여부를 체크한 뒤 방문 가능한 노드 개수를 반환한다.
• 주어진 coumputers 배열을 순회하면서 해당 인덱스의 방문 여부를 체크하는 것이 중요하다. 그렇지 않으면 무한 루프에 빠지게 되므로.. 일단 visited라는 배열을 만들고 초기 값은 false로 준다. 방문한 곳은 해당 인덱스에 값을 true로 변경하여 방문 처리를 한다.
• 만약 연결된 노드가 있고(즉, computers[i][j] == 1), 방문하지 않았다면 다시 재귀 함수를 통해 뻗어 나가면서 방문 처리를 한다.
  • 방문처리 순서를 설명하면 다음과 같다. (예제 1번 적용)
    1. 첫 번째로 computers의 0번 인덱스를 방문하고, 0번 노드를 방문 처리 한다.
    2. 0번 인덱스의 요소를 하나씩 방문하는데 연결되어있고 방문하지 않았으면 방문한다.
    3. computers[0]을 방문하면 computers[0][1]을 방문하게 되는 순서가 오고 그러면 computers[1]로 가게된다.
    4. 따라서 computers[0]와 computers[1]을 방문 후 dfs()를 빠져나오고, 다음으로 다시 dfs()를 실행하여 computers[2]를 방문한다.
• 마지막으로, 만약 하나의 컴퓨터에서 dfs()를 하면 해당 컴퓨터와 동일한 네트워크 상에 있는 모든 컴퓨터를 순회하게 되므로, DFS를 실행한 횟수가 곧 네트워크의 개수가 된다. 따라서, dfs()를 할 때마다 answer를 증가시키고 반환한다.

✅ 답안

function solution(n, computers) {
  let answer = 0;
  let visited = [false];

  function dfs(node) {
    visited[node] = true; // 현재 노드 방문 처리
    for (let i = 0; i < computers.length; i++) {
      if (computers[node][i] == 1 && !visited[i]) dfs(i);
      // 연결된 노드가 있고 해당 노드를 방문하지 않았다면, dfs로 방문 진행
    }
  }

  for (let i = 0; i < computers.length; i++) {
    if (!visited[i]) {
      // 방문하지 않은 노드에서 dfs 탐색, dfs실행할 때마다 answer++
      dfs(i);
      answer++;
    }
  }

  return answer;
}