전체 목록
알고리즘Medium#31

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)의 차이점과 활용 사례를 설명해주세요.

#알고리즘#그래프#DFS#BFS
힌트

스택/재귀 vs 큐, 탐색 순서의 차이를 생각해보세요.

정답 및 해설

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)의 차이점과 활용 사례를 설명해주세요.

DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프와 트리를 탐색하는 두 가지 기본 알고리즘입니다. DFS는 한 방향으로 끝까지 탐색한 후 되돌아오고(백트래킹), BFS는 현재 위치에서 가장 가까운 노드들을 먼저 모두 탐색합니다. 두 알고리즘의 탐색 방식 차이가 각각의 적합한 활용 사례를 결정합니다.

그래프 기본 개념

# 인접 리스트(Adjacency List)로 표현한 그래프
graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6, 7],
    4: [],
    5: [],
    6: [],
    7: []
}

#       1
#      / \
#     2   3
#    / \ / \
#   4  5 6  7

DFS (깊이 우선 탐색)

동작 원리

DFS는 스택(Stack) 자료구조를 사용하며, 한 방향으로 끝까지 내려간 뒤 되돌아와(백트래킹) 다른 경로를 탐색합니다.

탐색 순서 (위 그래프, 노드 1에서 시작):
1 → 2 → 4 (더 이상 없음) → 백트래킹
           → 5 (더 이상 없음) → 백트래킹
       → 3 → 6 (더 이상 없음) → 백트래킹
           → 7 (더 이상 없음) → 완료

결과: 1, 2, 4, 5, 3, 6, 7

재귀를 이용한 DFS 구현

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()

    visited.add(node)
    print(node, end=" ")

    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

    return visited

# 사용 예시
graph = {1: [2, 3], 2: [4, 5], 3: [6, 7], 4: [], 5: [], 6: [], 7: []}
dfs_recursive(graph, 1)  # 1 2 4 5 3 6 7

스택을 이용한 반복적 DFS 구현

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()  # LIFO - 가장 최근 노드부터

        if node not in visited:
            visited.add(node)
            print(node, end=" ")

            # 인접 노드를 역순으로 추가 (재귀와 동일한 순서 보장)
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

dfs_iterative(graph, 1)  # 1 2 4 5 3 6 7

DFS의 시간/공간 복잡도

  • 시간 복잡도: O(V + E) - 모든 정점(V)과 간선(E)을 한 번씩 방문
  • 공간 복잡도: O(V) - 방문 배열 + 재귀 호출 스택 (최대 깊이 d)

DFS 활용 사례

1. 경로 탐색

def find_path(graph, start, end, path=None):
    """시작 노드에서 끝 노드까지의 경로 찾기"""
    if path is None:
        path = []

    path = path + [start]

    if start == end:
        return path

    for neighbor in graph[start]:
        if neighbor not in path:  # 사이클 방지
            new_path = find_path(graph, neighbor, end, path)
            if new_path:
                return new_path

    return None  # 경로 없음

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [], 'E': [], 'F': []
}
print(find_path(graph, 'A', 'E'))  # ['A', 'B', 'E']

2. 사이클 감지

def has_cycle_directed(graph):
    """방향 그래프에서 사이클 감지"""
    WHITE, GRAY, BLACK = 0, 1, 2  # 미방문, 탐색 중, 완료
    color = {node: WHITE for node in graph}

    def dfs(node):
        color[node] = GRAY  # 탐색 시작

        for neighbor in graph[node]:
            if color[neighbor] == GRAY:  # 현재 경로에서 다시 만남 = 사이클
                return True
            if color[neighbor] == WHITE:
                if dfs(neighbor):
                    return True

        color[node] = BLACK  # 탐색 완료
        return False

    return any(dfs(node) for node in graph if color[node] == WHITE)

3. 위상 정렬 (Topological Sort)

def topological_sort(graph):
    """방향 비순환 그래프(DAG)의 위상 정렬"""
    visited = set()
    result = []

    def dfs(node):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor)
        result.append(node)  # 완료 후 추가 (역순)

    for node in graph:
        if node not in visited:
            dfs(node)

    return result[::-1]  # 뒤집으면 위상 정렬 순서

# 빌드 의존성 예시
graph = {'A': ['C'], 'B': ['C', 'D'], 'C': ['E'], 'D': ['F'], 'E': [], 'F': []}
print(topological_sort(graph))  # 의존 순서대로 출력

4. 미로 탐색 (백트래킹)

def solve_maze(maze, start, end):
    """미로에서 출구 찾기 (1=벽, 0=통로)"""
    rows, cols = len(maze), len(maze[0])
    visited = set()
    path = []

    def dfs(r, c):
        if (r, c) == end:
            return True
        if (r < 0 or r >= rows or c < 0 or c >= cols or
                maze[r][c] == 1 or (r, c) in visited):
            return False

        visited.add((r, c))
        path.append((r, c))

        # 4방향 탐색
        for dr, dc in [(0,1), (1,0), (0,-1), (-1,0)]:
            if dfs(r+dr, c+dc):
                return True

        path.pop()  # 백트래킹
        return False

    if dfs(start[0], start[1]):
        return path
    return None

BFS (너비 우선 탐색)

동작 원리

BFS는 큐(Queue) 자료구조를 사용하며, 현재 노드와 인접한 모든 노드를 먼저 탐색한 뒤 다음 레벨로 넘어갑니다.

탐색 순서 (위 그래프, 노드 1에서 시작):
레벨 0: 1
레벨 1: 2, 3
레벨 2: 4, 5, 6, 7

결과: 1, 2, 3, 4, 5, 6, 7 (레벨 순서)

BFS 구현

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])

    while queue:
        node = queue.popleft()  # FIFO - 가장 오래된 노드부터
        print(node, end=" ")

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

graph = {1: [2, 3], 2: [4, 5], 3: [6, 7], 4: [], 5: [], 6: [], 7: []}
bfs(graph, 1)  # 1 2 3 4 5 6 7

BFS의 시간/공간 복잡도

  • 시간 복잡도: O(V + E)
  • 공간 복잡도: O(V) - 큐에 최대 한 레벨의 노드 수 저장

BFS 활용 사례

1. 최단 경로 탐색 (가중치 없는 그래프)

def shortest_path(graph, start, end):
    """BFS로 최단 경로 탐색 (간선 가중치 없을 때)"""
    if start == end:
        return [start]

    visited = {start: None}  # 노드: 이전 노드 (경로 추적용)
    queue = deque([start])

    while queue:
        node = queue.popleft()

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited[neighbor] = node  # 이전 노드 저장
                queue.append(neighbor)

                if neighbor == end:
                    # 경로 역추적
                    path = []
                    current = end
                    while current is not None:
                        path.append(current)
                        current = visited[current]
                    return path[::-1]

    return None  # 경로 없음

graph = {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': []}
print(shortest_path(graph, 'A', 'F'))  # ['A', 'C', 'F'] (최단 2개 간선)

2. 레벨 순서 탐색 (트리)

def level_order_traversal(root):
    """트리의 레벨 순서 탐색"""
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        level = []

        for _ in range(level_size):  # 현재 레벨의 노드 모두 처리
            node = queue.popleft()
            level.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(level)

    return result

# 결과: [[1], [2, 3], [4, 5, 6, 7]]

3. 소셜 네트워크 거리 계산 (6단계 분리)

def degrees_of_separation(social_graph, person1, person2):
    """두 사람 사이의 최소 연결 거리"""
    if person1 == person2:
        return 0

    visited = {person1}
    queue = deque([(person1, 0)])

    while queue:
        person, distance = queue.popleft()

        for friend in social_graph.get(person, []):
            if friend == person2:
                return distance + 1
            if friend not in visited:
                visited.add(friend)
                queue.append((friend, distance + 1))

    return -1  # 연결 없음

social = {
    'Alice': ['Bob', 'Carol'],
    'Bob': ['Alice', 'Dave'],
    'Carol': ['Alice', 'Eve'],
    'Dave': ['Bob'],
    'Eve': ['Carol']
}
print(degrees_of_separation(social, 'Alice', 'Dave'))  # 2 (Alice-Bob-Dave)

DFS vs BFS 비교

탐색 순서 시각화

그래프:
        1
       / \
      2   3
     / \   \
    4   5   6

DFS 탐색 순서: 1 → 2 → 4 (막힘, 백트래킹) → 5 (막힘, 백트래킹) → 3 → 6
결과: [1, 2, 4, 5, 3, 6]

BFS 탐색 순서: 레벨0: 1 → 레벨1: 2, 3 → 레벨2: 4, 5, 6
결과: [1, 2, 3, 4, 5, 6]

언제 DFS를 쓸까? BFS를 쓸까?

# DFS가 적합한 경우: 존재 여부 확인, 백트래킹이 필요한 경우
def exists_path_dfs(graph, start, end):
    visited = set()
    def dfs(node):
        if node == end: return True
        visited.add(node)
        return any(dfs(n) for n in graph[node] if n not in visited)
    return dfs(start)

# BFS가 적합한 경우: 최단 거리가 필요한 경우
def shortest_distance_bfs(graph, start, end):
    queue = deque([(start, 0)])
    visited = {start}
    while queue:
        node, dist = queue.popleft()
        if node == end: return dist
        for n in graph[node]:
            if n not in visited:
                visited.add(n)
                queue.append((n, dist + 1))
    return -1

DFS vs BFS 최종 비교표

특성DFSBFS
자료구조스택 (재귀 가능)큐
탐색 방향깊이 우선너비 우선
시간 복잡도O(V+E)O(V+E)
공간 복잡도O(h) h=높이O(w) w=최대 너비
최단 경로보장 안 됨보장됨 (가중치 없을 때)
사이클 감지적합가능
위상 정렬적합가능
경로 탐색적합 (백트래킹)가능
레벨 순서 탐색어려움자연스러움
메모리 (밀집 트리)효율적비효율적
활용 예미로, 순열, DFS 기반 정렬최단 경로, 네트워크 거리
이전 질문다음 질문