[알고리즘] BFS, DFS

혜써클이 떴습니다☀️·2024년 11월 12일

자료구조 및 알고리즘

목록 보기

6/8

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

그래프를 탐색하는 알고리즘:

루트 노드에서부터 하나의 방향을 설정하여 리프 노드까지 탐색

그 후엔, 마지막 분기점으로 돌아와 다시 다른 방향으로 끝까지 탐색을 반복함
+) 분기: 하나의 노드에서 여러 개의 자식 노드로 갈 수 있는 경우
+) 분기점: 트리나 그래프에서 한 노드에 여러 자식 노드가 연결되어있을 때 해당 노드를 지칭하는 말 (탐색의 분기점 역할)

과정:
1. 한 분기를 다음 분기로 넘어가기 전까지 완벽하게 탐색
2. 분기에서 더이상 탐색 진행이 불가능하면, 이전 분기로 돌아와 다음 분기를 탐색
3. 모든 정점을 방문한 후, 탐색을 종료

1. 스택 이용

https://velog.io/@hyecircle/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-DFS-Inorder-Traversal

https://velog.io/@hyecircle/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-DFS-Postorder-Traversal

https://velog.io/@hyecircle/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-DFS-Preorder-Traversal
: 이전 벨로그 참고

function dfs(graph, start, visited) {
  const stack = [];
  stack.push(start);

  while (stack.length) {
    let v = stack.pop();
    if (!visited[v]) {
      console.log(v);
      visited[v] = true;

      for (let node of graph[v]) {
        if (!visited[node]) {
          stack.push(node);
        }
      }
    }
  }
}
const graph = [[1, 2, 4], [0, 5], [0, 5], [4], [0, 3], [1, 2]];
const visited = Array(7).fill(false);

dfs(graph, 0, visited);
// 0 4 3 2 5 1

2. 재귀함수 이용

const dfs = (graph, v, visited) => {
  // 현재 노드를 방문 처리
  visited[v] = true;
  console.log(v);

  // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for (let node of graph[v]) {
    if (!visited[node]) {
      dfs(graph, node, visited);
    }
  }
}

const graph = [[1, 2, 4], [0, 5], [0, 5], [4], [0, 3], [1, 2]];
const visited = Array(7).fill(false);

dfs(graph, 0, visited);
// 0 1 5 2 4 3

장단점:

장점
- 현재 경로의 노드를 기억함 -> 적은 메모리 사용
- 찾으려는 노드가 깊은 단계에 있는 경우 BFS보다 상대적으로 빠름
단점
- 해가 없는 경로를 탐색할 경우 단계가 끝날 때까지 탐색함
- 효율성 고려 X: DFS를 통해 얻은 해가 최단 경로가 아닐 수 있음

문제 유형:

방문 기록을 남기는 방향으로 문제 풀이
"백트래킹" 자주 이용: 더 이상 탐색할 필요가 없을 때, 앞에서 선택한 노드로 되돌아와 탐색을 반복
끝까지 갈 때 이용
특정 영역/깊이까지 가고싶을 때 길이를 정하거나, 구분되는 영역 설정

BFS(Breath-First Searc): 너비 우선 탐색

루트 노드을 방문한 후, 해당 정점과 인접한 모든 정점들을 우선적으로 탐색하는 방법

레벨별로 방문한다고 생각하면 됨

과정:
시작 노드를 먼저 큐에 넣고, 큐가 비어질 때까지 아래의 과정 반복
1. 큐에 저장된 정점을 하나 dequeue
2. dequeue한 정점과 연결된 모든 정점들을 큐에 push

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"]
};

// graph 자료구조와 startNode를 입력
const BFS = (graph, startNode) => {
  let visited = []; // 탐색을 마친 노드들
  let needVisit = []; // 탐색해야할 노드들

  needVisit.push(startNode); // 노드 탐색 시작

  while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
    const node = needVisit.shift(); // 가장 오래 남아있던 정점을 뽑아냄.
    if (!visited.includes(node)) { // 해당 노드 방문이 처음이라면,
      visited.push(node); 
      needVisit = [...needVisit, ...graph[node]];
    }
  }
  return visited;
};

console.log(BFS(graph, "A"));
// ["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]