자바스크립트로 DFS / BFS 완벽 정복하기

A : DFS/BFS 가 뭔지 알아 ?

Me : 그럼 ! DFS 는 그래프를 깊이 우선 탐색하는 것이고  , BFS는 그래프를 너비 우선 탐색하는거잖아 !

A: 자세히 설명해봐 뭔소린지 모르겠어 ! 

Me : DFS 는 특정 노드에서 시작해서 특정 노드와 연결된 모든 노드를 탐색한 후 다음 노드를 탐색하는거고 BFS는 특정 노드에서 시작해서 특정 노드와 인접한 노드들을 탐색한 후 그 다음 인접한 노드를 탐색하는거야 !! 그래프를 머리에 떠올려보면 DFS는 수직방향으로 BFS는 수평방향으로 진행한다고 생각해 나는 ! 

A: 오 ! 그럼 DFS/BFS 관련 문제는 다 풀수있겠네 ? 

Me: .... 아니 

 

현재 나는 DFS 와 BFS의 개념은 알고 있지만 이를 이용한 문제는 잘 풀지 못한다. 문제를 읽고 어떤걸 사용하는게 더 좋은지 잘 모르고있다. 그래서 이번 포스팅을 통해 DFS / BFS 를 완벽하게 이해하고 자바스크립트로 어떻게 구현하는지 , 어떤 문제에 어울리는지 이해하고 넘어가고자 한다.  

---

DFS  (깊이 우선 탐색 ) 구현하기 

DFS는 스택과 재귀함수로 구현할 수 있다. 

1. 재귀로 구현하기 

//재귀로 구현 
function dfs(node, visited) {
    if (visited[node]) return;

    visited[node] = true;
    console.log(node);

    for (let neighbor of graph[node]) {
        dfs(neighbor, visited);
    }
}

// 사용 예시
const graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6],
    4: [],
    5: [7],
    6: [],
    7: []
};

const visited = {};
dfs(1, visited);

 

그래프

1

/ \

2    3

/ \    / 

4  5  6   

/   

7     

 

dfs 함수 동작 설명 

1. 만약 현재 노드가 이미 방문된 노드라면 함수를 종료한다. 방문 여부는 visited 객체를 통해 관리된다.
2. 현재 노드를 방문했다면, 해당 노드를 방문한 것으로 표시하고(visited[node] = true), 현재 노드를 출력한다(console.log(node)).
3. 현재 노드와 연결된 모든 이웃 노드에 대해 dfs 함수를 재귀적으로 호출한다.

실행 결과 

 

---

2. 스택으로 구현하기 

function dfsWithStack(start) {
    const visited = {};
    const stack = [start];

    while (stack.length > 0) {
        const node = stack.pop();

        if (visited[node]) break;

        visited[node] = true;
        console.log(node);

        for (let neighbor of graph[node]) {
            if (!visited[neighbor]) {
                stack.push(neighbor);
            }
        }
    }
}

// 사용 예시
const graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6],
    4: [],
    5: [7],
    6: [],
    7: []
};

dfsWithStack(1);

 

dfs 함수 동작 설명 

1. stack 배열을 사용하여 현재 노드에서 다음에 방문할 노드를 추적한다.
2. while 루프는 스택이 비어있을 때까지 계속 실행한다.
3. 스택에서 노드를 꺼내와서 이전에 방문한 노드인지 확인한다. 만약 이미 방문한 노드라면 무시하고 다음 반복으로 넘어간다.
4. 현재 노드를 방문했다면, 해당 노드를 출력하고 방문했음을 표시한다.
5. 현재 노드와 연결된 이웃 노드들 중에서 아직 방문하지 않은 노드를 스택에 추가한다.

실행결과 

 

---

BFS  (너비 우선 탐색 ) 구현하기 

BFS는 큐로 구현할 수 있다. 

function bfs(graph, start) {
  // 방문 여부를 저장하는 배열
  let visited = {};

  // 큐를 초기화하고 시작 노드를 추가
  let queue = [start];
  visited[start] = true;

  // 큐가 비어질 때까지 반복
  while (queue.length !== 0) {
    // 큐에서 노드를 꺼내와서 출력하거나 원하는 작업 수행
    let current = queue.shift();
    console.log(current);

    // 현재 노드와 연결된 이웃 노드들을 방문하지 않은 경우 큐에 추가하고 방문 여부 표시
    for (let neighbor of graph[current]) {
      if (!visited[neighbor]) {
        queue.push(neighbor);
        visited[neighbor] = true;
      }
    }
  }
}

// 예시 그래프
const graph = {
  1: [2, 3],
  2: [4, 5],
  3: [6],
  4: [],
  5: [7],
  6: [],
  7: []
};

// 시작 노드를 1로 설정하여 BFS 실행
bfs(graph, 1);

 

bfs 함수 동작 설명 

1. 현재 노드에서 다음에 방문할 노드를 추적하기 위해 큐 배열을 활용
2. 큐가 비어있을 때까지 계속해서 반복한다다.
3. 큐에서 노드를 꺼내와서 이전에 방문한 노드인지 확인한다다. 이미 방문한 노드라면 무시하고 다음 반복으로 넘어간다.
4. 현재 노드를 방문했다면 해당 노드를 출력하고 방문했음을 표시한다.
5. 현재 노드와 연결된 이웃 노드 중에서 아직 방문하지 않은 노드를 큐에 추가한다.

 

실행결과

 

 

---

어떤 상황에서 BFS  / DFS 를 적용하면 좋을까 ? 

DFS, BFS은 특징에 따라 사용에 더 적합한 문제 유형들이 있다.

• 그래프의 모든 정점을 방문하는 것이 주요한 문제
  단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다.
  둘 중 편한 것을 사용하시면 됩니다.
• 경로의 특징을 저장해둬야 하는 문제
  예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)
• 최단거리 구해야 하는 문제
  미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.
  왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,
  너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.

이밖에도

• 검색 대상 그래프가 정말 크다면 DFS를 고려
• 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS

 

(https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90  참고)