📚 문제

dfs/bfs - 네트워크
https://programmers.co.kr/learn/courses/30/lessons/43162

💡 접근

그래프 탐색 알고리즘

• BFS (Breadth First Search)
  • 너비 우선 탐색
  • 너비 = 층
  • 이전 노드와 연결된 노드를 먼저 탐색해야하기 때문에 큐 자료구조를 사용한다.
  • root와 가까운 node들부터 찾기 때문에 최단거리를 탐색할 때 유용하다.
• DFS (Depth First Search)
  • 깊이 우선 탐색
  • 정점의 자식들부터 순차적으로 탐색
  • 이전노드가 아니라 자기자신과 연결된 노드를 먼저 탐색하기 때문에 스택 자료구조를 사용한다.
  • BFS보다 속도가 느릴 수 있다.
  • 경로가 존재하는지를 판별할 때 유용하다.

1. 모든 노드를 방문해야하기 때문에 방문한 것을 기록할 check 배열을 컴퓨터 개수만큼 만든다.
2. dfs 내부에서는 현재 노드를 방문한 것을 check하고 현재 노드와 연결된 노드를 살펴보고 연결된 노드가 있는데 방문하지 않았으면 dfs를 재귀호출한다.
3. 연결된 노드는 한번의 dfs로 모두 방문할 수 있으므로 dfs 밖에서 dfs를 호출한 횟수를 세면 네트워크 개수를 구할 수 있다.

⌨️ 코드

function solution(n, computers) {
  let check = [];
  let network = 0;

  for (let i = 0; i < computers.length; i++) {
    check[i] = false;
  }

  function dfs(index) {
    check[index] = true;

    for (let i = 0; i < computers.length; i++) {
      if (computers[index][i] == 1 && !check[i]) {
        dfs(i);
      }
    }
  }

  for (let i = 0; i < computers.length; i++) {
    if (!check[i]) {
      dfs(i);
      network++;
    }
  }

  return network;
}

📝 리뷰

dfs/bfs 너무 어려워서 다른 분 코드 참고했다..ㅜㅜ