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

📌 문제

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

📌 풀이

function solution(n, computers) {
  var ans = 0;
  let visited = new Array(n + 1).fill(0);

  function DFS(start) {
    visited[start] = 1;
    for (let i = 0; i < computers.length; i++) {
      if (computers[start][i] === 1 && visited[i] === 0) {
        DFS(i);
      }
    }
  }
  for (let i = 0; i < n; i++) {
    if (visited[i]) continue;
    else {
      DFS(i);
      ans++;
    }
  }
  return ans;
}

✔ 알고리즘 : DFS

✔ 노드 방문 처리를 위한 1차원 배열 visited 선언

✔ computers[start][i] 가 1 이면 start 노드에서 i 노드가 이어져있다 && visited[i]가 0이면 아직 방문하지 않은 노드이므로 DFS(i)로 탐색을 이어감

✔ 방문처리는 DFS탐색을 시작할 때 visited[start]=1로 해줌

✔ for문으로 노드수만큼 돌면서 방문된 상태면 진행하고 아니면 DFS탐색

✔ ans는 DFS가 처음 시작할때만 1증가 , DFS안에서 DFS가 호출될때는 ans 증가 X

✔ 난이도 : 프로그래머스 기준 LEVEL 3