그래프 탐색 - DFS와 BFS

계산 중... 0
Computer Science Algorithms Graph
DFS BFS Graph Traversal

미로를 탈출한다고 상상해보세요. 두 가지 전략이 있습니다.

  1. 한 길을 끝까지 가보고, 막히면 되돌아오기 → DFS (깊이 우선 탐색)
  2. 현재 위치에서 갈 수 있는 모든 곳을 먼저 확인하기 → BFS (너비 우선 탐색)

저는 처음 배울 때 “둘 다 결국 모든 곳을 탐색하는데 왜 두 개나 있지?”라고 생각했습니다. 하지만 실제로 사용해보니, 각자 잘하는 것이 다르다는 걸 깨달았습니다.

왜 그래프 탐색을 배워야 할까요?

1. 실무에서 정말 많이 사용

  • 소셜 네트워크: “친구의 친구” 찾기
  • 파일 시스템: 폴더 구조 탐색
  • 웹 크롤러: 링크 따라가기
  • 게임 AI: 경로 찾기
  • 추천 시스템: 연관 상품 찾기

2. 많은 문제의 기초

그래프 탐색을 이해하면 다음을 배우기 쉽습니다.

  • 최단 경로 (다익스트라)
  • 사이클 감지
  • 위상 정렬
  • 연결 요소 찾기

3. 코딩 테스트 단골 주제

LeetCode Medium 문제의 30% 이상이 그래프 탐색을 사용합니다.

그래프란?

실생활 예시

소셜 네트워크:
Alice ─── Bob
  │        │
  │        │
Charlie ─ David

도시 간 도로:
서울 ──200km── 부산
  │              │
100km          150km
  │              │
대전 ──100km── 대구

그래프 표현 방법

인접 리스트 (Adjacency List) - 가장 많이 사용

const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D'],
  'C': ['A', 'D'],
  'D': ['B', 'C']
};

인접 행렬 (Adjacency Matrix)

const graph = [
  [0, 1, 1, 0],  // A와 연결: B, C
  [1, 0, 0, 1],  // B와 연결: A, D
  [1, 0, 0, 1],  // C와 연결: A, D
  [0, 1, 1, 0]   // D와 연결: B, C
];

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

핵심 아이디어

“한 길을 끝까지 가보고, 막히면 되돌아온다”

미로 탐색 비유:
1. 오른쪽 길로 쭉 간다
2. 막히면? 왔던 길로 돌아가서
3. 다른 길을 시도

시각화

그래프:
    A
   / \
  B   C
  |   |
  D   E

DFS 순서:
A → B → D (막힘, 되돌아감)
  → C → E (막힘, 되돌아감)

결과: A, B, D, C, E

스택(Stack)으로 동작

스택: [A]
pop A → 방문 ✅
push B, C

스택: [B, C]
pop B → 방문 ✅
push D

스택: [D, C]
pop D → 방문 ✅

스택: [C]
pop C → 방문 ✅
push E

스택: [E]
pop E → 방문 ✅

스택: [] → 끝!

JavaScript 구현 - 재귀 버전

function dfs(graph, start, visited = new Set()) {
  // 1. 현재 노드 방문
  console.log(start);
  visited.add(start);

  // 2. 인접 노드들을 재귀적으로 탐색
  for (const neighbor of graph[start] || []) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited);
    }
  }

  return visited;
}

// 사용 예시
const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D'],
  'C': ['A', 'E'],
  'D': ['B'],
  'E': ['C']
};

dfs(graph, 'A');
// 출력: A, B, D, C, E

JavaScript 구현 - 스택 버전

function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];

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

    if (visited.has(node)) continue;

    console.log(node);
    visited.add(node);

    // 이웃들을 스택에 추가
    const neighbors = graph[node] || [];
    for (let i = neighbors.length - 1; i >= 0; i--) {
      if (!visited.has(neighbors[i])) {
        stack.push(neighbors[i]);
      }
    }
  }

  return visited;
}

DFS 실전 활용

1. 경로 존재 여부 확인

function hasPath(graph, start, target) {
  if (start === target) return true;

  const visited = new Set();
  const stack = [start];

  while (stack.length > 0) {
    const node = stack.pop();
    if (node === target) return true;

    if (visited.has(node)) continue;
    visited.add(node);

    for (const neighbor of graph[node] || []) {
      stack.push(neighbor);
    }
  }

  return false;
}

console.log(hasPath(graph, 'A', 'E'));  // true
console.log(hasPath(graph, 'A', 'Z'));  // false

2. 모든 경로 찾기

function findAllPaths(graph, start, target, path = [], paths = []) {
  path.push(start);

  if (start === target) {
    paths.push([...path]);
  } else {
    for (const neighbor of graph[start] || []) {
      if (!path.includes(neighbor)) {
        findAllPaths(graph, neighbor, target, path, paths);
      }
    }
  }

  path.pop();
  return paths;
}

const allPaths = findAllPaths(graph, 'A', 'E');
console.log(allPaths);  // [['A', 'C', 'E']]

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

핵심 아이디어

“가까운 곳부터 차례대로 탐색한다”

물결 퍼지기 비유:
    시작점 (0)
   /    |    \
 (1)   (1)   (1)  ← 거리 1
  |     |     |
 (2)   (2)   (2)  ← 거리 2

시각화

그래프:
    A
   / \
  B   C
  |   |
  D   E

BFS 순서:
Level 0: A
Level 1: B, C
Level 2: D, E

결과: A, B, C, D, E

큐(Queue)로 동작

큐: [A]
dequeue A → 방문 ✅
enqueue B, C

큐: [B, C]
dequeue B → 방문 ✅
enqueue D

큐: [C, D]
dequeue C → 방문 ✅
enqueue E

큐: [D, E]
dequeue D → 방문 ✅

큐: [E]
dequeue E → 방문 ✅

큐: [] → 끝!

JavaScript 구현

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];

  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift();  // 큐에서 꺼냄
    console.log(node);

    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);  // 큐에 추가
      }
    }
  }

  return visited;
}

bfs(graph, 'A');
// 출력: A, B, C, D, E

BFS 실전 활용

1. 최단 경로 찾기

function shortestPath(graph, start, target) {
  const visited = new Set();
  const queue = [[start, [start]]];  // [노드, 경로]

  visited.add(start);

  while (queue.length > 0) {
    const [node, path] = queue.shift();

    if (node === target) {
      return path;  // 최단 경로 발견!
    }

    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, [...path, neighbor]]);
      }
    }
  }

  return null;  // 경로 없음
}

console.log(shortestPath(graph, 'A', 'E'));
// ['A', 'C', 'E']

2. 레벨별 순회 (층별 탐색)

function levelOrder(graph, start) {
  const levels = [];
  const visited = new Set();
  const queue = [[start, 0]];  // [노드, 레벨]

  visited.add(start);

  while (queue.length > 0) {
    const [node, level] = queue.shift();

    if (!levels[level]) {
      levels[level] = [];
    }
    levels[level].push(node);

    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, level + 1]);
      }
    }
  }

  return levels;
}

console.log(levelOrder(graph, 'A'));
// [['A'], ['B', 'C'], ['D', 'E']]

3. 소셜 네트워크 - 2촌 친구 찾기

function friendsOfFriends(graph, person, maxDegree = 2) {
  const visited = new Set();
  const queue = [[person, 0]];
  const result = [];

  visited.add(person);

  while (queue.length > 0) {
    const [current, degree] = queue.shift();

    if (degree > 0 && degree <= maxDegree) {
      result.push(current);
    }

    if (degree < maxDegree) {
      for (const friend of graph[current] || []) {
        if (!visited.has(friend)) {
          visited.add(friend);
          queue.push([friend, degree + 1]);
        }
      }
    }
  }

  return result;
}

const socialNetwork = {
  'Alice': ['Bob', 'Charlie'],
  'Bob': ['Alice', 'David'],
  'Charlie': ['Alice', 'Eve'],
  'David': ['Bob'],
  'Eve': ['Charlie']
};

console.log(friendsOfFriends(socialNetwork, 'Alice', 2));
// ['Bob', 'Charlie', 'David', 'Eve']

DFS vs BFS 비교

언제 DFS를 사용할까?

✅ DFS가 좋은 경우:

1. 모든 경로를 찾아야 할 때

// 예: 미로의 모든 탈출 경로
findAllPaths(maze, start, exit);

2. 메모리가 제한적일 때

// DFS: O(깊이) 메모리
// BFS: O(너비) 메모리
// 깊은 트리에서는 DFS가 유리

3. 경로 자체가 중요할 때

// 백트래킹 문제
// N-Queens, Sudoku 등

언제 BFS를 사용할까?

✅ BFS가 좋은 경우:

1. 최단 경로를 찾을 때

// BFS는 항상 최단 경로를 보장!
shortestPath(graph, 'A', 'Z');

2. 가까운 노드부터 확인해야 할 때

// 예: 가장 가까운 병원 찾기
findNearestHospital(map, currentLocation);

3. 레벨/거리가 중요할 때

// 예: 6촌 이내의 친구 찾기
findFriendsWithinDegree(friends, 'Alice', 6);

비교표

항목 DFS BFS
자료구조 스택 (Stack) 큐 (Queue)
메모리 O(h) 높이 O(w) 너비
최단 경로 ❌ 보장 안 됨 ✅ 보장됨
구현 재귀 or 스택 큐
속도 비슷 비슷
사용 예 백트래킹, 경로 찾기 최단 경로, 레벨 탐색

실수하기 쉬운 함정

함정 1: 방문 체크 빼먹기

// ❌ 무한 루프!
function dfsWrong(graph, start) {
  console.log(start);

  for (const neighbor of graph[start]) {
    dfsWrong(graph, neighbor);  // 방문 체크 없음!
  }
}

// ✅ 올바른 코드
function dfsCorrect(graph, start, visited = new Set()) {
  if (visited.has(start)) return;

  console.log(start);
  visited.add(start);

  for (const neighbor of graph[start]) {
    dfsCorrect(graph, neighbor, visited);
  }
}

함정 2: BFS에서 queue.pop() 사용

// ❌ 잘못된 BFS (DFS가 됨!)
while (queue.length > 0) {
  const node = queue.pop();  // 스택처럼 동작!
}

// ✅ 올바른 BFS
while (queue.length > 0) {
  const node = queue.shift();  // 큐처럼 동작!
}

함정 3: 방문 체크 시점

// ❌ 중복 방문 가능
function bfsWrong(graph, start) {
  const visited = new Set();
  const queue = [start];

  while (queue.length > 0) {
    const node = queue.shift();
    visited.add(node);  // 너무 늦음!

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        queue.push(neighbor);
      }
    }
  }
}

// ✅ 큐에 넣을 때 방문 체크
function bfsCorrect(graph, start) {
  const visited = new Set([start]);  // 시작 시 체크
  const queue = [start];

  while (queue.length > 0) {
    const node = queue.shift();

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);  // 큐에 넣을 때 체크!
        queue.push(neighbor);
      }
    }
  }
}

연습 문제

1. 섬의 개수 세기

// 2D 그리드에서 연결된 1의 개수 세기
const grid = [
  [1, 1, 0, 0, 0],
  [1, 1, 0, 0, 1],
  [0, 0, 0, 1, 1],
  [0, 0, 0, 0, 0]
];

function countIslands(grid) {
  // DFS 또는 BFS 사용
  // 힌트: 각 1을 만날 때마다 연결된 모든 1을 방문 처리
}

2. 최단 거리 계산

function shortestDistance(graph, start, target) {
  // BFS 사용하여 거리 반환
  // 힌트: 각 노드와 함께 거리를 저장
}

3. 사이클 감지

function hasCycle(graph) {
  // DFS 사용하여 사이클 존재 여부 확인
  // 힌트: 현재 경로에 있는 노드를 다시 방문하면 사이클
}

참고 자료

공식 문서 및 학술 자료

시각화 및 학습 도구

온라인 강의

실습 문제

관련 문서

응용 분야

실무 응용 사례

도서

  • Grokking Algorithms - Aditya Bhargava (그래프 챕터)
  • Algorithm Design Manual - Steven Skiena (Chapter 5: Graph Traversal)
  • The Algorithm Design Manual - 그래프 알고리즘 실전 예제

마치며

DFS와 BFS는 같은 목적, 다른 전략입니다.

  • DFS: 깊게 파고들기 → 백트래킹, 경로 찾기
  • BFS: 넓게 퍼지기 → 최단 경로, 레벨 탐색

처음에는 “언제 뭘 써야 하지?”가 헷갈리지만, 문제를 많이 풀다 보면 자연스럽게 느낌이 옵니다.

핵심은 “방문 체크”와 “자료구조 선택”입니다! 🎯

다음 단계

같은 레벨 (중급):

다음 레벨 (고급):

관련 자료구조:

🚀 추천 학습 순서: 이진 탐색 → 재귀 → DFS/BFS → 다익스트라 → 동적 프로그래밍

댓글