[알고리즘 코어 파헤치기] DFS & BFS 완벽 해부 - 그래프 탐색의 뼈대 세우기

학습 철학 회고
단순히 미로를 찾고 단지에 번호를 붙이는 1차원적인 풀이를 넘어, '그래프를 남김없이 탐색한다'는 본질적 목표를 어떻게 코드로 추상화할 것인지 고민했습니다. 특정 조건에 휘둘리지 않는, DFS와 BFS의 가장 순수하고 일반화된 뼈대(Skeleton)를 세웁니다.

📌 개념 요약: DFS와 BFS란 무엇인가?

데이터가 거미줄처럼 얽혀있는 그래프(Graph) 공간에서, 모든 정점을 단 한 번씩만, 누락 없이 방문하기 위한 두 가지 상반된 탐색 철학입니다.

• DFS (깊이 우선 탐색): "갈 수 있을 때까지 끝까지 파고든다." 막다른 길에 다다르면 직전 갈림길로 돌아와 다른 길을 찾습니다.
• BFS (너비 우선 탐색): "내 주변부터 꼼꼼하게 살핀다." 시작점에서 가까운 노드들을 모두 방문한 뒤, 점차 탐색 반경을 넓혀갑니다. 최단 거리를 보장하는 강력한 특징이 있습니다.

💡 동작 원리 및 자료구조의 선택

탐색의 순서를 결정하는 것은 결국 '어떤 자료구조(그릇)에 다음 방문할 곳을 담을 것인가'입니다.

1. DFS와 스택(Stack) / 재귀: 방금 발견한 새로운 길을 먼저 가야 하므로, 나중에 들어온 것을 먼저 꺼내는 LIFO(Last-In First-Out) 구조가 필요합니다. 파이썬에서는 별도의 스택 리스트보다는 재귀 함수(Recursion) 자체가 시스템 스택을 이용하므로 가장 우아한 구현 방식이 됩니다.
2. BFS와 큐(Queue): 먼저 발견한 가까운 길을 먼저 가야 하므로, 들어온 순서대로 꺼내는 FIFO(First-In First-Out) 구조가 필요합니다. 파이썬에서는 collections.deque를 사용하여 양방향 입출력을 $O(1)$로 최적화해야 합니다. 리스트의 pop(0)은 $O(N)$이 걸리므로 절대 사용해선 안 됩니다.

💻 추상화된 템플릿 코드

1. BFS (너비 우선 탐색) 템플릿

from collections import deque

def bfs_template(start, graph, visited):
    # 1. 큐 초기화 및 시작점 방문 처리
    queue = deque([start])
    visited[start] = True
    
    # 2. 큐가 빌 때까지 반복
    while queue:
        # 가장 먼저 들어온(가까운) 노드 꺼내기
        current = queue.popleft()
        print(f"현재 방문한 노드: {current}") # 핵심 로직 수행 위치
        
        # 3. 인접 노드 탐색
        for next_node in graph[current]:
            if not visited[next_node]:
                queue.append(next_node)
                visited[next_node] = True # [핵심] 큐에 넣을 때 반드시 방문 처리!

2. DFS (깊이 우선 탐색) 템플릿

def dfs_template(current, graph, visited):
    # 1. 현재 노드 방문 처리
    visited[current] = True
    print(f"현재 방문한 노드: {current}") # 핵심 로직 수행 위치
    
    # 2. 인접 노드 탐색
    for next_node in graph[current]:
        # 아직 방문하지 않은 노드가 있다면, 즉시 그곳으로 깊게 파고들기(재귀 호출)
        if not visited[next_node]:
            dfs_template(next_node, graph, visited)

🚨 설계 및 회고

• 방문 처리(Visited)의 시점: BFS에서 가장 많이 하는 실수가 노드를 큐에서 '꺼낼 때' 방문 처리를 하는 것입니다. 큐에 들어있는 상태에서도 다른 노드에 의해 중복으로 큐에 삽입될 수 있으므로, 반드시 '큐에 넣는 순간(발견한 순간)' 방문 처리를 해야 큐 폭발(메모리 초과)을 막을 수 있습니다.
• 모듈화의 이점: 이 순수한 뼈대 로직을 그대로 유지한 채, print 부분만 count += 1로 바꾸면 연결 요소의 개수를 구하는 문제가 되고, distance[next] = distance[current] + 1로 바꾸면 최단 거리 내비게이션으로 변신합니다.