[AL] BFS, DFS - JavaScript

코딩테스트, 각종 연습문제의 단골개념인 BFS, DFS에 대해서 다뤄보자🏃‍♀️

BFS, DFS 모두 정점(node)과 그 정점들을 연결하는 간선(edge)로 이루어진 그래프를 탐색할때 사용하는 방법이다. (그래프를 탐색한다는 것은 한 정점으로부터 시작해서 모든 정점을 한번씩 방문하는 것을 의미한다!)

사진출처

그림으로 두 방법의 탐색순서의 차이점에 대해 간단하게 살펴보자면,
BFS의 경우에는 node A에서 시작해서 node B -> node C -> node D -> ... node J에서 탐색이 끝난다.
최종적으로 [A, B, C, D, G, H, I, E, F, J]의 탐색 순서를 가지게 된다.

DFS의 경우에는 node A에서 시작해서 node B -> node D -> node E -> ... node J에서 탐색이 끝난다.
최종적으로 [A, B, D, E, F, C, G, H, I, J]의 탐색 순서를 가지게 된다.

BFS(Breadth-First Search, 너비 우선 탐색)

BFS : 시작정점에서부터 인접해 있는 노드를 우선으로 탐색하는 방법

• 두개의 큐를 사용하며, 주로 최단거리를 구하는 문제에 사용된다.

예제 코드

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'G', 'H', 'I'],
  D: ['B', 'E', 'F'],
  E: ['D'],
  F: ['D'],
  G: ['C'],
  H: ['C'],
  I: ['C', 'J'],
  J: ['I']
};

const bfs = (graph, start) => {
  let visited = [];  // 이미 방문한 노드 저장
  let needVisit = []; // 앞으로 탐색해야 하는 노드 저장 (queue로 구현해야함)
  
  needVisit.push(start);  // 시작노드부터 탐색 시작
  
  // 탐색해야 하는 노드가 아직 남아있다면
  while(needVisit.length !== 0){
    let node = needVisit.shift();  // 선입선출을 따라야하므로 shift로 node 선정
    if(!visited.includes(node)){  // 위의 node가 방문된 적이 없다면
      visited.push(node);
      needVist = [...needVisit, ...graph[node]]; // 기존의 (needVisit + 위의 노드의 자식들) 큐에 삽입
    }
  }
  return visited;
    

DFS(Depth-First Search, 깊이 우선 탐색)

DFS : 시작정점에서부터 해당 분기를 전부 탐색 한 후 다음 분기를 탐색하는 방법

• 한개의 큐, 한개의 스택을 사용하며, 주로 경로의 존재 여부를 판별하는 문제에 사용된다.

예제 코드

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'G', 'H', 'I'],
  D: ['B', 'E', 'F'],
  E: ['D'],
  F: ['D'],
  G: ['C'],
  H: ['C'],
  I: ['C', 'J'],
  J: ['I']
};

const dfs = (graph, start) => {
  let visited = []; // 이미 방문한 노드 저장 
  let needVisit = [];  // 앞으로 탐색해야 하는 노드 저장 (stack으로 구현해야함)
  
  needVisit.push(start);  // 시작노드부터 탐색 시작
  
  // 탐색해야 하는 노드가 아직 남아있다면
  while(needVisit.length !== 0){
    let node = needVisit.pop();  // stack이므로 뒤에서부터 선출
    if(!visited.includes(node)){
      visited.push(node);
      needVisit = [...needVisit, ...graph[node]];
    }
  }
  return visited;
}

실제 문제 적용

문제 링크

문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한 조건

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.
  
  
  입출력 예

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

DFS 풀이

function solution(n, computers) {
    let answer = 0;
    let visit = []; 
    
    // 방문 큐 생성
    for(let i=0; i<n; i++){
        visit.push(false);
    }
    
    function DFS(idx){
        visit[idx] = true;
        
        for(let i=0; i<n; i++){
            // 네트워크가 연결되어 있고, 아직 방문하지 않은 상태라면 
            // 해당 컴퓨터를 다시 DFS 수행
            if(computers[idx][i] === 1 && !visit[i]){
                DFS(i);
            }
        }
    }
    
    for(let i=0; i<n; i++){
        if(!visit[i]){
            DFS(i);
            answer++;
        }
    }
    return answer;
}

BFS 풀이

function solution(n, computers) {
    let answer = 0;
    let visit = []; 
    let needVisit = [];
    
    for(let i=0; i<n; i++){
        visit.push(false);
    }

    for(let i=0; i<n; i++){
        if(!visit[i]){
            needVisit.push(i);
            visit[i] = true;
            answer++;
            
            while(needVisit.length !== 0){
                let node = needVisit.shift();
                computers[node].forEach((e, idx) => {
                    if(idx !== node){
                        if(!visit[idx] && computers[node][idx] === 1){
                            visit[idx] = true;
                            needVisit.push(idx);
                        }
                    }
                });
            }
        }
    }
    

    return answer;
}