Graph - DFS, BFS 심화

연결된 정점들

문제
방향이 없는 간선들의 목록이 주어질 때,
연결된 정점의 컴포넌트(그룹들)가 몇 개인지 반환하는 함수를 작성하세요.
입력
인자 1: edges
2차원 Array 타입을 요소로 갖는 시작과 도착 정점이 담겨있는 배열들을 담고 있는 목록
ex) [[0, 1], [1, 2], [3, 4]]
출력
Number 타입을 리턴해야 합니다.
연결된 정점의 컴포넌트의 수를 숫자로 반환합니다.
주의사항
주어진 간선은 무향입니다
[1, 2] 는 정점 1에서 정점 2로도 갈 수 있으며, 정점 2에서 정점 1로도 갈 수 있습니다.

function connectedVertices(edges) {
  
  // 1. 주어진 정점을 통해 matrix를 완성하자.

  // 가장 큰 정점 찾기
  let biggestV = Math.max(...edges.flat())    
  // 최댓값으로 matrix 만들기
  let matrix = Array(biggestV + 1).fill(0)
  			.map((el) => Array(biggestV + 1).fill(0))

  // 매트릭스에 edges 반영하기 -> 간선 추가하기
  edges.forEach( edge => {
    let [from, to] = edge
    matrix[from][to] = 1;
    matrix[to][from] = 1;
  }) // 주어진 간선은 무향(쌍방)이다!
  
// -------------- 인접행렬 완성!
  
  let isVisited = [] // 중복 방지 배열
  let groups = 0; // 연결된 정점들을 하나의 그룹으로 만들 것이다.

  for (let start = 0; start < matrix.length; start++) {
    if (!isVisited.includes(start)) {
      dfs(matrix, start) // start와 연결된 정점을 다 탐색하고
      groups++; // 그것을 한 그룹으로 친다.
    }
  }

  function bfs(matrix, vertex) {
  let Q = [vertex];
      while (Q.length) {
        let now = Q.shift()
        isVisited.push(now)
        for (let next = 0; next < matrix[now].length; next++) {
          if(matrix[now][next] && !isVisited.includes(next)) {
            Q.push(next)
          }
        }
      }
    }

  function dfs(matrix, vertex) {
    isVisited.push(vertex)
    for (let next = 0; next < matrix[vertex].length; next++) {
      if (matrix[vertex][next] && !isVisited.includes(next)) {
      dfs(matrix, next)
      }
    }
  }
  return groups;
}

위 풀이의 경우 bfs, dfs 함수는 보조함수로,
connectedVertices 주 함수의 isVisited 변수에 접근할 수 있기 때문에
인자로 isVisited를 넣어 줄 필요가 없다.

function connectedVertices(edges) {
  
  let biggestV = Math.max(...edges.flat())    
  let matrix = Array(biggestV + 1).fill(0)
  		.map((el) => Array(biggestV + 1).fill(0))

  edges.forEach( edge => {
    let [from, to] = edge
    matrix[from][to] = 1;
    matrix[to][from] = 1;
  }) 
  
  let isVisited = []
  let groups = 0; 

  for (let start = 0; start < matrix.length; start++) {
    if (!isVisited.includes(start)) {
      bfs(matrix, start, isVisited) 
      groups++; 
    }
  }
  return groups;
}

function bfs(matrix, vertex, isVisited) {
  let Q = [vertex];
      while (Q.length) {
        let now = Q.shift()
        isVisited.push(now)
        for (let next = 0; next < matrix[now].length; next++) {
          if(matrix[now][next] && !isVisited.includes(next)) {
            Q.push(next)
          }
        }
      }
    }

  function dfs(matrix, vertex, isVisited) {
    isVisited.push(vertex)
    for (let next = 0; next < matrix[vertex].length; next++) {
      if (matrix[vertex][next] && !isVisited.includes(next)) {
      dfs(matrix, next, isVisited)
      }
    }
  }

위 풀이는 dfs, bfs 함수가 독립적이기 때문에
함께 사용하기 위해서는 인자로 isVisited 정보를 전달해줘야 한다.