코플릿_[DFS / BFS] 연결된 정점들

문제

방향이 있는 간선들의 목록이 주어질 때, 연결된 정점의 컴포넌트(그룹들)가 몇 개인지 반환하는 함수를 작성하세요.

입출력 예시

const result = connectedVertices([
  [0, 1],
  [2, 3],
  [3, 4],
  [3, 5],
]);
console.log(result); // 2

입력

2차원 Array 타입을 요소로 갖는 시작과 도착 정점이 담겨있는 배열들을 담고 있는 목록 (2차원 배열)
ex) [[0, 1], [1, 2], [3, 4]]

출력

연결된 정점의 컴포넌트의 수를 Number 타입으로 리턴

풀이

function connectedVertices(edges) {

  // reduce를 이용해 최대 버텍스를 탐색하는 함수 작성
  // maxVertex = 5 (입출력 예시 대입)
  const maxVertex = edges.reduce((a, c) => {
    const bigger = Math.max(...c);
    if (bigger > a) {
      return bigger; 
    } else {
      return a;
    }
  }, 0); // 기본값 : 0
  // 혹은 const maxVertex = Math.max(...edges.flat()); 

  // 최대 버텍스의 길이만큼 인접 리스트 생성
  const adjList = {};
  for (let i = 0; i <= maxVertex; i++) {
    adjList[i] = [];
  }
  // adjList = {
  //  "0": [],
  //  "1": [],
  //  "2": [],
  //  "3": [],
  //  "4": [],
  //  "5": []
  // }
  
  // 무향 그래프이므로 쌍방으로 연결해준다 
  for (let i = 0; i < edges.length; i++) {
    adjList[edges[i][0]].push(edges[i][1]);
    adjList[edges[i][1]].push(edges[i][0]);
  }
  // adjList = {
  //  "0": [1],
  //  "1": [0],
  //  "2": [3],
  //  "3": [2, 4, 5],
  //  "4": [3],
  //  "5": [3]
  // }
  // 인접 리스트 작성

  const visited = {}; // 방문한 버텍스 표시
  let count = 0; // 결과 출력을 위한 변수
  
  for (let vertex = 0; vertex <= maxVertex; vertex++) {
    // 버텍스 순회 (0 ~ 5)
    if (!visited[vertex]) { // 만약 방문한 적이 없는 정점이라면
      dfs(adjList, vertex, visited); // 순회 (dfs or bfs)
      count++; // 카운트 증가
    }
  }
  return count; // 최종 결과
}


function bfs(adjList, vertex, visited) {
  const queue = [vertex]; // 큐 생성 
  visited[vertex] = true; // 해당 vertex 체크
  // 만약 vertex가 3이라면 
  // queue = [3]
  
  while (queue.length > 0) {
    const cur = queue.shift(); 
    // cur = 3
    // queue = []
    for (let i = 0; i < adjList[cur].length; i++) {
      if (!visited[adjList[cur][i]]) { 
        queue.push(adjList[cur][i]);
        // queue = [4]
        // queue = [4, 5]
        visited[adjList[cur][i]] = true;
      }
    }
  }
}

function dfs(adjList, vertex, visited) {
  visited[vertex] = true; // 먼저 해당 vertex를 체크한다. 
  for (let i = 0; i < adjList[vertex].length; i++) {
    if (!visited[adjList[vertex][i]]) {
      // 만약 vertex가 3이라면 
      // adjList[3][1] = 4
      // adjList[3][2] = 5
      dfs(adjList, adjList[vertex][i], visited);
    } 
  }
}

console.log(connectedVertices([
  [0, 1],
  [2, 3],
  [3, 4],
  [3, 5],
])); // 2

전체 과정은 다음과 같이 나누어 볼 수 있다.

1. 출력 값을 설정한다. (count)
2. 최대 버텍스의 길이를 구한다. (maxVertex)
3. 구한 길이를 토대로 인접 리스트 틀을 만든다. (adjList)
4. 주어진 edges에 기초해 인접 리스트를 작성한다.
5. 버텍스를 체크하며 순회한다. 순회가 완료되면 카운트를 1 증가시킨다. (dfs, bfs 이용)
6. 카운트를 리턴한다.

여기서도 역시 bfs는 queue를, dfs는 재귀를 이용하는 것을 볼 수 있다.