[백준] 18511, 1260, 2606 / DFS, BFS 정리 / JavaScript

DFS와 BFS의 실전적 이해: 백준 문제 풀이를 통한 완전 탐색 전략

들어가며

백준 문제를 풀면서 Greedy, DP 문제를 풀다가 드디어 항상 어려워했던 DFS, BFS 문제로 넘어오게 되었습니다. 완전 탐색 문제들을 풀면서 상황에 따라 DFS, BFS를 사용해야 할 필요를 느꼈고, 항상 개념만 알고 코드로 풀어내는 경험이 부족했던 것 같아서 정리하면서 글로 작성해보려고 합니다.

DFS와 BFS의 기본 개념

간단하게 이해하자면:

• DFS(깊이 우선 탐색): 경우의 수를 구할 때 그래프를 그린다면 나올 수 있는 가장 깊은 곳까지 갔다가 돌아오는 느낌
• BFS(너비 우선 탐색): 경우의 수를 구할 때 그래프를 그린다면 한 층씩 마무리해가면서 다음 단계로 넘어가는 느낌

코드로 보는 실제 구현

실제 구현에서 DFS와 BFS는 확연한 차이를 보입니다. 아래 코드를 통해 자세히 살펴보겠습니다.

기본 설정

const fs = require('fs');
const filePath = process.platform === 'linux' ? 'dev/stdin' : '../input.txt';
const input = fs.readFileSync(filePath).toString().trim().split('\n');

let [N, M, V] = input[0].split(' ').map(Number);
let graph = Array.from({ length: N }, () => []);

// 그래프 구성
for (let i = 1; i < M + 1; i++) {
  let [a, b] = input[i].split(' ').map(Number);
  graph[a - 1].push(b - 1);
  graph[b - 1].push(a - 1);
}

// 그래프 정렬
for (let i = 0; i < N; i++) {
  graph[i].sort((a, b) => a - b);
}

DFS 구현

let visited = new Array(N).fill(false);
let dfsLog = [];

function dfs(node) {
  dfsLog.push(node + 1);
  visited[node] = true;

  for (let nextNode of graph[node]) {
    if (!visited[nextNode]) {
      dfs(nextNode);
    }
  }
}

BFS 구현

function bfs(node) {
  let queue = [node];
  visited[node] = true;
  let bfsLog = [];

  while (queue.length > 0) {
    let curNode = queue.shift();
    bfsLog.push(curNode + 1);

    for (let nextNode of graph[curNode]) {
      if (!visited[nextNode]) {
        queue.push(nextNode);
        visited[nextNode] = true;
      }
    }
  }

  return bfsLog;
}

구현의 핵심 차이점

1. 자료구조 활용

• DFS: 재귀 호출을 통한 시스템 스택 활용
• BFS: 큐(Queue) 자료구조를 명시적으로 활용

2. 탐색 방식

• DFS: 한 경로를 끝까지 탐색한 후 백트래킹
• BFS: 현재 깊이의 모든 노드를 탐색 후 다음 깊이로 이동

3. 메모리 사용

• DFS:
  • 재귀 호출로 인한 콜 스택 사용
  • 깊이가 깊은 경우 스택 오버플로우 주의
• BFS:
  • 큐에 저장되는 노드 수만큼의 메모리 사용
  • 너비가 넓은 그래프에서 메모리 사용량 증가

실제 활용 시나리오

DFS가 유리한 경우

1. 모든 경로를 탐색해야 하는 경우
   • 미로의 모든 경로 찾기
   • 게임의 모든 가능한 상태 탐색
2. 백트래킹이 필요한 문제
   • N-Queens 문제
   • 순열/조합 생성

BFS가 유리한 경우

1. 최단 경로 찾기
   • 미로에서 출구까지의 최단 거리
   • 최소 이동 횟수 구하기
2. 레벨 단위 탐색
   • 그래프의 계층 구조 분석
   • SNS에서의 친구 관계 단계 분석

마무리

항상 어렵다고 생각했었는데 하나씩 체크해나가면서 정리를 다시 하니 금방 머리에 들어오는 것 같습니다. DFS의 경우, 상황에 따라서 백트래킹이 필요한 경우도 있기 때문에 해당 부분이 있는 문제도 풀어보고 내용을 추가해보려고 합니다.

참고자료

• 백준 온라인 저지의 DFS/BFS 문제들