프로그래머스 JS [네트워크] DFS

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

프로그래머스

---

문제 요약

 

네트워크는 연결되어 있는 컴퓨터들의 집합입니다.

전체 네트워크의 수를 확인하시오.

---

문제 풀이

 

// 1,2,3,... 각각의 노드에서 이후의 번호에 대해 연결된 곳을 찾기

// 연결된 숫자들에 대해서는 재탐색을 하지 않음

// 이 뒤로 연결된 네트워크가 없을 경우에는 네트워크 카운트 +1

 

 

function solution(n, computers) {

  var answer = 0;

  let checkedComputersArray = Array(n).fill(false);

  for (let i = 0; i < n; i++) {

    if (!checkedComputersArray[i]) {

      // i번째 computersArray확인

      const stack = [i];

      while (stack.length) {

        // 확인한 nthComputer는 확인처리

        const nthComputer = stack.pop();

        if (!checkedComputersArray[nthComputer]) {

          checkedComputersArray[nthComputer] = true;

          // 확인이 가능한 computersArray의 nthComputer가 방문가능한 computerArray에 방문
          // 현재 computerArray의 nthComputer가 1일 경우 nthComputersArray[nthComputer] 또한 반드시 1

          for (let j = 0; j < n; j++) {

            if (computers[nthComputer][j] && !checkedComputersArray[j]) {

              stack.push(j);

            }

          }

        }

      }

      answer++;

    }

  }

  return answer;

}