E-2: DFS와 BFS — 그래프 위를 걷는 두 걸음걸이

안녕하세요, 여러분의 알고리즘 길잡이 홍순구 튜터입니다. 지난 시간엔 카테고리 E의 문을 열며 완전탐색과 그 뼈대인 재귀, 그리고 헛일을 줄이는 백트래킹을 익혔습니다. "영리한 지름길이 없으면 다 뒤진다"는 정신으로 부분집합·순열·조합을 빠짐없이 만들어 봤죠. 그때 우리가 뒤진 무대는 "1부터 n까지의 숫자" 같은 추상적인 나열이었습니다.

오늘은 그 완전탐색을 훨씬 생생한 무대 위에서 합니다. 바로 C-3에서 배운 그래프(정점과 간선) 위예요. 미로에서 출구를 찾고, 지도에서 섬의 개수를 세고, 친구의 친구까지 몇 다리 건너면 닿는지를 구하는 문제들 — 이게 전부 "그래프를 탐색하는" 일입니다. 지난 시간의 재귀 호출 스택이 오늘 DFS로, B-1에서 배운 큐(deque)가 오늘 BFS로 곧장 이어집니다. 두 개념을 잘 챙겨 왔다면 오늘은 그걸 그래프 위에 얹기만 하면 돼요.

 오늘의 여정 — 그래프 위를 두 걸음걸이로 걷는다

   방문 체크(visited)    같은 정점을 두 번 밟지 않는 장치 — 사이클에서 무한 루프 방지
     │
     ├─ DFS(깊이 우선)    한 길로 끝까지 파고들다 막히면 되돌아온다
     │     ├─ 재귀        지난 시간의 호출 스택이 그대로 걸음이 된다
     │     └─ 스택        재귀를 명시적 스택으로 갈아 끼운다
     │
     └─ BFS(너비 우선)    가까운 곳부터 물결처럼 넓게 퍼진다
           ├─ 큐(deque)   B-1의 큐로 레벨 순 방문
           └─ 최단 거리   가중치 없는 그래프에선 BFS가 곧 최단
     ▼
   무대 둘              추상 그래프(인접 리스트) · 격자(2차원 배열, 상하좌우)

💡 오늘 수업의 핵심 — "방문 체크로 무한 루프를 막고, DFS로 깊게·BFS로 넓게 그래프를 훑되, 가중치 없는 최단 경로는 BFS로 구한다"

🎯 학습 목표

• 방문 체크(visited)로 사이클에서 무한 루프를 막고, 그래프의 모든 정점을 한 번씩 방문한다.
• DFS(재귀·스택)와 BFS(큐)로 그래프를 훑고, 연결 요소와 격자(섬의 개수)로 굳힌다.
• 가중치 없는 그래프에서 BFS가 왜 최단 경로를 주는지 이해하고, 미로 최단거리를 구한다.

Step 1: "다 방문하되, 두 번은 안 돼" (그래프 탐색과 방문 체크)

그래프 탐색(graph traversal)이란 한마디로 "그래프의 모든 정점을 빠짐없이, 그리고 한 번씩만 방문하는 것"입니다. 친구 관계망에서 나와 이어진 사람을 전부 찾거나, 미로에서 갈 수 있는 칸을 모두 밟아 보는 일이 전부 탐색이에요.

그래프는 C-3에서 배운 대로 인접 리스트(adjacency list)로 담습니다. 정점마다 "이 정점과 이어진 이웃 목록"을 들고 있는 방식이죠. 파이썬에선 딕셔너리 하나면 됩니다.

# 정점 0~5, 각 정점의 이웃 목록. C-3에서 만든 그 인접 리스트다.
g = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 4],
    3: [1, 5],
    4: [2, 5],
    5: [3, 4],
}

이제 정점 0에서 출발해 이어진 정점을 따라 걷는다고 해 봅시다. 0의 이웃 1로 가고, 1의 이웃 0으로 돌아오고, 다시 0에서 1로… 눈치채셨나요? 그래프엔 트리와 달리 사이클(cycle, 돌아오는 길)이 있어서, 아무 장치 없이 이웃을 따라가면 같은 정점을 오가며 영원히 돕니다.

 방문 표시가 없으면 — 사이클에서 영원히 돈다

   0 ─ 1        0 → 1 → 0 → 1 → 0 → …  무한 반복
   │            이미 밟은 0으로 자꾸 되돌아온다

 방문 표시(visited)를 달면 — 이미 밟은 정점은 건너뛴다

   0(밟음) → 1(밟음) → 3 → 5 → 4 → 2 → 끝
   되돌아온 0·1은 "이미 방문"이라 그냥 지나친다

그래서 탐색의 심장은 방문 체크(visited)입니다. 한 번 밟은 정점을 집합(set)이나 배열에 기록해 두고, 이미 방문한 곳은 다시 들어가지 않는 것. 이 한 줄이 무한 루프를 막습니다. 오늘 배울 DFS와 BFS는 "어떤 순서로 방문하느냐"만 다를 뿐, 둘 다 이 방문 체크 위에 섭니다.

두 걸음걸이가 어떻게 다른지 미리 그려 볼게요.

 같은 그래프, 다른 걸음걸이

        0            DFS(깊이 우선): 0 → 1 → 3 → 5 → 4 → 2
       / \              한 줄기로 바닥(5)까지 내려갔다 되돌아 나온다
      1   2
      |   |          BFS(너비 우선): 0 → 1,2 → 3,4 → 5
      3   4              가까운 이웃(1,2)부터 한 겹씩 넓힌다
       \ /
        5

두 방식 모두 정점 V개를 한 번씩 방문하고(각 O(1)), 간선 E개를 인접 리스트로 한 번씩 훑습니다. 그래서 시간 복잡도는 둘 다 O(V+E)예요. 이 과목의 척추인 빅오로 보면, 그래프 탐색은 "정점 수 더하기 간선 수"만큼 걸리는 아주 효율적인 알고리즘입니다. 선형이라 정점·간선이 각각 수십만이어도 "1초에 1억 연산" 잣대로 넉넉히 통과해요. 이제 깊이 우선부터 손으로 짜 봅시다.

💡 한 줄 정리

그래프 탐색은 모든 정점을 한 번씩 방문하는 일이고, 그 심장은 방문 체크(visited)다. 그래프엔 사이클이 있어 방문 표시를 안 하면 같은 정점을 오가며 무한 루프에 빠진다. DFS와 BFS는 방문 순서만 다를 뿐, 둘 다 O(V+E)에 방문 체크 위에서 돈다.

Step 2: "끝까지 파고든다" (DFS — 재귀)

DFS(depth-first search, 깊이 우선 탐색)는 이름 그대로입니다. 한 방향으로 갈 수 있는 데까지 끝까지 파고들었다가, 막다른 곳에 닿으면 한 걸음 되돌아 나와 다른 길을 갑니다. 미로에서 "일단 한 방향으로 쭉 가 보고, 벽에 막히면 되돌아 나오는" 그 방식이에요.

이 "파고들었다 되돌아온다"는 흐름, 지난 시간에 이미 봤습니다. 바로 재귀예요. 지금 정점을 방문하고, 아직 안 가 본 이웃마다 자기 자신을 다시 부르면, 되돌아옴(백트래킹)은 재귀가 끝나며 호출 스택이 풀리는 것으로 저절로 일어납니다.

# algorithms/dfs_bfs.py
def dfs_recursive(graph, start, visited=None, order=None):
    if visited is None:
        visited = set()
        order = []
    visited.add(start)              # 지금 정점을 방문 표시 — 다시 안 밟도록
    order.append(start)             # 방문 순서 기록
    for nxt in graph.get(start, []):
        if nxt not in visited:      # 안 가 본 이웃으로만 더 깊이
            dfs_recursive(graph, nxt, visited, order)
    return order

핵심은 딱 세 줄입니다. 지금 정점을 visited에 넣고, 이웃을 하나씩 보되 아직 방문 안 한 이웃이면 그 이웃으로 재귀 호출. 지난 시간의 팩토리얼이 factorial(n-1)을 불렀듯, 여기선 dfs_recursive(graph, nxt, ...)를 부릅니다. 다른 건 "무엇을 향해 파고드느냐"뿐이에요.

Step 1의 그래프에서 정점 0부터 어떻게 파고드는지 따라가 봅시다.

 dfs_recursive(g, 0) — 지난 시간처럼 호출이 쌓였다 풀린다

   0 방문 → 이웃 1로 파고
     1 방문 → 이웃 3으로 파고
       3 방문 → 이웃 5로 파고
         5 방문 → 이웃 4로 파고
           4 방문 → 이웃 2로 파고
             2 방문 → 더 갈 곳 없음 ┐
   ← ← ← ← 호출 스택 거꾸로 풀림 ← ┘ (unwind)

   방문 순서: 0 → 1 → 3 → 5 → 4 → 2

실제로 dfs_recursive(g, 0)을 실행하면 [0, 1, 3, 5, 4, 2]가 나옵니다. 한 줄기(0-1-3-5)로 바닥까지 내려갔다가, 되돌아 나오며 남은 4, 2를 훑는 게 눈에 보이죠?

시간 복잡도는 O(V+E)입니다. 정점마다 한 번씩 방문하고(V), 각 정점에서 이웃(간선)을 한 번씩 훑으니(E) 둘을 더한 만큼이에요. 공간은 O(V)입니다. visited 집합이 최대 V개, 그리고 재귀 호출 스택이 최악의 경우(정점이 일자로 쭉 이어진 그래프) 깊이 V까지 쌓이거든요.

실전 코딩테스트에선 이 재귀 DFS를 그대로 씁니다. 다만 그래프가 깊으면 재귀 깊이 한계에 걸리는데, 그 이야기는 바로 다음 Step이에요.

💡 한 줄 정리

DFS는 한 길로 끝까지 파고들었다 막히면 되돌아 나오는 탐색이고, 그 흐름이 곧 재귀다. 지금 정점을 방문 표시하고 안 가 본 이웃마다 자기를 다시 부르면, 되돌아옴은 호출 스택이 풀리며 저절로 일어난다. 시간 O(V+E), 공간 O(V).

Step 3: "재귀를 스택으로 갈아 끼운다" (DFS — 스택)

재귀 DFS는 우아하지만 약점이 하나 있습니다. 지난 시간에 봤듯 파이썬은 재귀 깊이를 약 1000으로 제한해요. 정점이 10만 개인 일자 그래프를 재귀로 파고들면 RecursionError가 납니다. 이럴 때 두 가지 길이 있어요. 하나는 재귀 한계를 늘리는 것(sys.setrecursionlimit), 다른 하나는 아예 재귀를 안 쓰고 반복문으로 바꾸는 겁니다.

여기서 중요한 통찰: 재귀 DFS가 쓰던 "호출 스택"을, 우리가 직접 list로 들고 다니면 재귀 없이 똑같은 DFS가 됩니다. 재귀가 암묵적으로 쓰던 스택을 명시적 스택으로 갈아 끼우는 거예요.

# algorithms/dfs_bfs.py
def dfs_stack(graph, start):
    visited = set()
    order = []
    stack = [start]
    while stack:
        node = stack.pop()          # 가장 최근에 쌓은 정점을 꺼낸다(LIFO)
        if node in visited:         # 이미 방문했으면 헛걸음 — 건너뛴다
            continue
        visited.add(node)
        order.append(node)
        for nxt in reversed(graph.get(node, [])):   # 역순으로 쌓아 재귀와 순서를 맞춘다
            if nxt not in visited:
                stack.append(nxt)
    return order

스택은 B-1에서 배운 후입선출(LIFO) 자료구조죠. 나중에 쌓은 걸 먼저 꺼냅니다. 그래서 이웃을 그냥 쌓으면 마지막 이웃부터 파고들어 재귀와 순서가 뒤집혀요. 이웃을 reversed로 역순으로 쌓아 주면 재귀 DFS와 똑같은 순서가 됩니다.

 스택(list)으로 직접 — 재귀의 호출 스택을 손에 든다

   pop 0  방문      이웃 역순(2,1) push → stack: [2, 1]
   pop 1  방문      이웃(3) push      → [2, 3]
   pop 3  방문      이웃(5) push      → [2, 5]
   pop 5  방문      이웃(4) push      → [2, 4]
   pop 4  방문      이웃(2) push      → [2, 2]
   pop 2  방문      (윗 2 먼저 꺼냄, 남은 2는 pop 시 "이미 방문"이라 건너뜀)

   방문 순서: 0 → 1 → 3 → 5 → 4 → 2   ← 재귀와 똑같다

dfs_stack(g, 0)도 [0, 1, 3, 5, 4, 2]를 돌려줍니다. 재귀 버전과 글자 그대로 같은 결과예요.

한 가지 눈여겨볼 점. 같은 정점이 스택에 두 번 쌓일 수 있습니다(위에서 2가 두 번 들어갔죠). 그래서 꺼낼 때 "이미 방문했으면 건너뛴다"는 검사를 반드시 넣어요. 이게 없으면 같은 정점을 여러 번 기록합니다. 시간·공간 복잡도는 재귀 버전과 같은 O(V+E)·O(V)이고, 다만 재귀 깊이 한계에 안 걸리는 게 이 반복 버전의 이점입니다.

정리하면, 얕은 그래프는 재귀 DFS가 짧고 읽기 좋아 실전에서 자주 씁니다. 아주 깊어질 위험이 있으면 sys.setrecursionlimit으로 한계를 늘리거나, 이 스택 버전으로 바꿔 터짐을 피해요.

💡 한 줄 정리

재귀 DFS의 호출 스택을 직접 list로 들고 다니면 반복문 DFS가 된다. 스택은 LIFO라 이웃을 역순으로 쌓아야 재귀와 순서가 같아지고, 같은 정점이 두 번 쌓일 수 있어 꺼낼 때 방문 검사를 한다. 재귀 깊이 한계(약 1000)에 안 걸리는 게 이점이다.

Step 4: "가까운 곳부터 넓게" (BFS — 큐)

DFS가 "한 길로 끝까지"라면, BFS(breadth-first search, 너비 우선 탐색)는 정반대입니다. 시작 정점에서 가까운 이웃부터 한 겹씩 넓게 퍼져 나가요. 마치 잔잔한 물에 돌을 던지면 파문이 동심원으로 퍼지듯, 거리 1인 정점을 다 방문한 다음 거리 2, 그다음 거리 3으로 나아갑니다.

깊이 우선이 스택(나중에 온 걸 먼저)을 썼다면, 너비 우선은 큐(먼저 온 걸 먼저)를 씁니다. B-1에서 배운 그 선입선출(FIFO) 큐예요. 파이썬에선 collections.deque를 큐로 씁니다.

# algorithms/dfs_bfs.py
from collections import deque

def bfs(graph, start):
    visited = {start}               # 큐에 넣는 순간 방문 표시(중복 인큐 방지)
    order = []
    queue = deque([start])
    while queue:
        node = queue.popleft()      # 앞에서 꺼낸다(FIFO)
        order.append(node)
        for nxt in graph.get(node, []):
            if nxt not in visited:
                visited.add(nxt)    # 꺼낼 때가 아니라 넣을 때 표시
                queue.append(nxt)
    return order

흐름은 이렇습니다. 시작 정점을 큐에 넣고, 큐에서 하나 꺼내 방문하며, 그 정점의 안 가 본 이웃을 큐 뒤에 붙입니다. 먼저 넣은 게 먼저 나오니 시작에서 가까운 정점부터 처리돼요.

 큐(deque)로 넓게 — 넣은 순서대로 꺼낸다(FIFO)

   pop 0  방문      이웃 1,2 enqueue → queue: [1, 2]
   pop 1  방문      이웃 3   enqueue → [2, 3]
   pop 2  방문      이웃 4   enqueue → [3, 4]
   pop 3  방문      이웃 5   enqueue → [4, 5]
   pop 4  방문      (5는 이미 큐에 있어 안 넣음)
   pop 5  방문

   방문 순서: 0 → 1,2 → 3,4 → 5   ← 레벨 순(가까운 정점부터)

bfs(g, 0)은 [0, 1, 2, 3, 4, 5]를 돌려줍니다. DFS의 [0, 1, 3, 5, 4, 2]와 확연히 다르죠? 거리별로 겹을 이뤄 퍼지는 게 보입니다.

 BFS는 '거리별 겹'으로 퍼진다

   겹 0:        0          (거리 0)
   겹 1:      1   2        (거리 1)
   겹 2:      3   4        (거리 2)
   겹 3:        5          (거리 3)

여기서 딱 하나 꼭 지킬 규칙이 있습니다. 방문 표시를 "큐에서 꺼낼 때"가 아니라 "큐에 넣을 때" 해야 해요. 만약 꺼낼 때 표시하면, 같은 정점이 여러 이웃을 통해 큐에 중복으로 들어갈 수 있습니다. 위 그림에서 5는 3을 통해 큐에 들어가는데, 넣을 때 바로 표시해 두니 4에서 다시 넣으려 할 때 걸러집니다. 이 한 끗이 BFS의 흔한 버그를 막아요.

시간·공간 복잡도는 DFS와 같은 O(V+E)·O(V)입니다. deque의 popleft와 append는 양 끝 연산이라 O(1)이라, 큐로서 효율이 완벽해요.

💡 한 줄 정리

BFS는 가까운 이웃부터 한 겹씩 넓게 퍼지는 탐색이고, 큐(FIFO)로 구현한다. 먼저 넣은 정점이 먼저 나와 거리 순으로 방문된다. 방문 표시는 '큐에 넣는 순간' 해야 같은 정점이 중복으로 들어가지 않는다. 시간 O(V+E), 공간 O(V).

Step 5: "따로 노는 덩어리 세기" (연결 요소)

지금까지는 한 정점에서 출발해 "거기서 닿을 수 있는" 정점을 훑었습니다. 그런데 그래프가 여러 덩어리로 쪼개져 있으면 어떨까요? 친구 관계망을 떠올려 보세요. 서로 이어진 무리가 여럿이고, 무리끼리는 아무 연결도 없을 수 있습니다. 이 "서로 이어진 덩어리 하나하나"를 연결 요소(connected component)라고 부릅니다.

연결 요소의 개수를 세는 아이디어는 간단하고 우아합니다. 정점을 0번부터 차례로 보면서, 아직 방문 안 한 정점을 만나면 "새 덩어리를 발견했다!"고 개수를 하나 올리고, 거기서 탐색을 시작해 그 덩어리를 통째로 방문 표시합니다. 새 탐색이 시작되는 횟수가 곧 덩어리의 수예요.

# algorithms/dfs_bfs.py
def count_components(num_vertices, edges):
    graph = {v: [] for v in range(num_vertices)}
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)          # 무방향: 양쪽에 서로를 넣는다

    visited = set()
    count = 0
    for v in range(num_vertices):
        if v not in visited:        # 아직 어느 덩어리에도 안 든 정점
            count += 1              # 새 덩어리 발견
            for node in bfs(graph, v):
                visited.add(node)   # 이 덩어리 전체를 방문 표시
    return count

바깥 for문이 정점을 하나씩 훑고, 이미 방문한 정점은 그냥 지나칩니다. 아직 방문 안 한 정점을 만나야만 새 탐색(여기선 BFS)을 돌려요. 그 탐색이 한 덩어리를 싹 방문 표시하니, 같은 덩어리의 다른 정점은 바깥 루프에서 자동으로 걸러집니다.

 정점을 차례로 보며, 새 덩어리를 만날 때마다 +1

   0 ─ 1 ─ 2   ← 덩어리 A (새 탐색 1회째, count 1)
   3 ─ 4       ← 덩어리 B (새 탐색 2회째, count 2)
   5           ← 덩어리 C (고립, count 3)

count_components(6, [(0,1), (1,2), (3,4)])를 실행하면 3이 나옵니다. 0-1-2가 한 덩어리, 3-4가 또 한 덩어리, 그리고 아무와도 안 이어진 5가 홀로 한 덩어리, 이렇게 셋이에요.

여기서 DFS를 써도 결과는 똑같습니다. "덩어리를 통째로 방문 표시"만 하면 되니, 깊게 파든 넓게 퍼지든 상관없어요. 시간 복잡도는 O(V+E)입니다. 바깥 루프가 정점을 V번 훑고, 탐색 전체가 모든 간선을 한 번씩 보니까요. 이 "바깥 루프 + visited" 골격은 다음 Step의 격자 문제에서 거의 그대로 다시 등장합니다.

💡 한 줄 정리

연결 요소는 서로 이어진 정점 덩어리다. 정점을 차례로 보며 아직 방문 안 한 정점을 만날 때마다 개수를 올리고 그 덩어리를 통째로 탐색해 표시하면, 새 탐색이 시작된 횟수가 곧 덩어리 수다. DFS든 BFS든 결과는 같고, 시간은 O(V+E).

Step 6: "지도 위를 걷는다" (격자 탐색·섬의 개수)

지금까진 그래프가 인접 리스트로 주어졌습니다. 그런데 코딩테스트에서 그래프 탐색이 가장 자주 나오는 형태는 사실 따로 있어요. 바로 격자(grid), 즉 2차원 배열입니다. 미로, 지도, 이미지 픽셀 — 전부 격자로 주어지고, 그 위를 탐색하는 문제가 쏟아집니다.

격자를 그래프로 보는 관점이 열쇠예요. 격자의 한 칸이 정점이고, 상하좌우로 붙은 이웃 칸이 간선입니다. 인접 리스트가 따로 없어도, 좌표 계산만으로 이웃을 찾을 수 있어요.

 격자 = 칸이 정점, 상하좌우 이웃이 간선

              (r-1, c)  위
                 │
   (r, c-1) ─ (r, c) ─ (r, c+1)   왼쪽 · 지금 칸 · 오른쪽
                 │
              (r+1, c)  아래

   네 방향 델타(행 변화, 열 변화): (-1,0) (1,0) (0,-1) (0,1)

지금 칸 (r, c)에서 상하좌우 이웃은 행·열에 (-1,0)·(1,0)·(0,-1)·(0,1)을 더한 좌표예요. 이 네 개의 변화량을 델타(delta)라고 부르고, 보통 상수로 빼 둡니다.

이제 코테 최빈출 문제인 "섬의 개수"를 풀어 봅시다. 1은 땅, 0은 바다인 격자에서, 상하좌우로 이어진 1의 덩어리 하나가 섬 하나예요. 섬이 몇 개인지 세는 겁니다. 눈치채셨겠지만, 이건 Step 5의 연결 요소 세기를 격자 위에서 하는 것과 완전히 같은 골격입니다.

# algorithms/dfs_bfs.py
# 격자에서 상·하·좌·우 네 방향. (행 변화, 열 변화)
DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def count_islands(grid):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    count = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and not visited[r][c]:
                count += 1                          # 새 섬 발견
                queue = deque([(r, c)])             # 이 섬을 BFS로 번져 나간다
                visited[r][c] = True
                while queue:
                    cr, cc = queue.popleft()
                    for dr, dc in DIRECTIONS:
                        nr, nc = cr + dr, cc + dc
                        # 격자 밖으로 나가지 않고, 땅(1)이며, 아직 안 밟은 칸만
                        if 0 <= nr < rows and 0 <= nc < cols \
                                and grid[nr][nc] == 1 and not visited[nr][nc]:
                            visited[nr][nc] = True
                            queue.append((nr, nc))
    return count

바깥 이중 for문이 모든 칸을 훑고, 아직 방문 안 한 땅(1)을 만나면 섬 개수를 올린 뒤 거기서 BFS로 그 섬을 통째로 번져 나갑니다. 이웃을 찾을 때 DIRECTIONS로 상하좌우를 더하고, 세 가지를 반드시 확인해요. 격자 밖으로 나가지 않았는지(경계 검사), 땅인지, 아직 안 밟았는지. 이 경계 검사(0 <= nr < rows)를 빼먹으면 배열 범위를 벗어나 에러가 나니 꼭 챙기세요.

 섬 세기 — 상하좌우로 이어진 1의 덩어리

   1 1 0 0 0        땅(1) 덩어리 다섯:
   1 1 0 0 1          A: 좌상단 2×2 블록
   0 0 0 1 1          B: 오른쪽 (1,4)-(2,4)-(2,3)
   0 0 0 0 0          C: (4,0)
   1 0 1 0 1          D: (4,2)    E: (4,4)

위 격자에 count_islands를 돌리면 5가 나옵니다. 대각선은 이어진 것으로 치지 않아요(상하좌우만 봤으니까). 만약 대각선까지 한 섬으로 치는 문제라면 DIRECTIONS에 네 대각선 (-1,-1)·(-1,1)·(1,-1)·(1,1)을 더해 여덟 방향으로 넓히면 됩니다. 이렇게 방향 배열만 바꿔 규칙을 조정하는 게 격자 탐색의 묘미예요.

시간·공간 복잡도는 O(H×W)입니다(H는 행 수, W는 열 수). 모든 칸을 정확히 한 번씩 방문하니까요. 격자에선 정점 수 V가 곧 칸 수 H×W이고, 간선도 그에 비례해 O(H×W)로 묶입니다. 섬의 개수, 단지번호붙이기, 미로 탐색 — 코테의 그래프 문제 상당수가 이 격자 골격 위에 서 있어요.

💡 한 줄 정리

격자는 칸이 정점, 상하좌우 이웃이 간선인 그래프다. 방향 델타 배열로 이웃을 찾고, 경계·땅·미방문 세 조건을 확인하며 번진다. 섬의 개수는 연결 요소 세기를 격자에서 하는 것과 같은 골격이고, 시간·공간은 O(H×W).

Step 7: "몇 걸음이면 닿나" (최단 경로 BFS)

이제 BFS의 진짜 위력을 볼 차례입니다. 지금까진 "방문 순서"에 집중했지만, BFS가 코딩테스트에서 사랑받는 진짜 이유는 따로 있어요. 바로 가중치 없는 그래프에서 최단 경로를 공짜로 준다는 겁니다.

왜 그럴까요? BFS는 시작 정점에서 한 걸음(간선 하나) 거리를 다 방문한 뒤, 두 걸음 거리, 세 걸음 거리로 겹겹이 넓혀 갑니다. 그러니 어떤 정점에 처음 도착한 순간의 걸음 수가 곧 그 정점까지의 최단 거리예요. 나중에 다른 길로 더 짧게 닿을 수가 없습니다. 먼저 닿았다는 건 더 가까웠다는 뜻이니까요.

 가중치 없는 그래프 — 처음 닿은 순간이 곧 최단

   BFS는 거리 1 → 거리 2 → 거리 3 순으로 퍼진다.
   어떤 정점에 '처음' 도착한 겹이 그 정점의 최단 거리다.
   (나중 겹에서 다시 만나도 이미 방문 표시라 갱신 안 함)

   시작 0 기준 거리:  0→0  1→1  2→1  3→2  4→2  5→3

각 정점까지의 최단 거리를 담아 돌려주는 BFS를 짜 봅시다. 방문 표시 대신 "몇 걸음 만에 닿았나"를 딕셔너리에 적으면, 그게 방문 표시와 거리 기록을 겸합니다.

# algorithms/dfs_bfs.py
def bfs_distances(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph.get(node, []):
            if nxt not in dist:             # 아직 안 닿은 정점 = 지금이 최단
                dist[nxt] = dist[node] + 1  # 한 걸음 더
                queue.append(nxt)
    return dist

dist에 키가 있으면 이미 방문한 것이고, 없으면 아직 안 닿은 정점입니다. 새로 닿을 때 "지금 정점의 거리 + 1"을 적어요. bfs_distances(g, 0)은 {0:0, 1:1, 2:1, 3:2, 4:2, 5:3}을 돌려줍니다. 정점 5는 세 걸음 거리로 정확히 잡혔죠.

이 아이디어를 격자에 얹으면 코테 단골 "미로 최단거리"가 됩니다. 0은 길, 1은 벽인 미로에서 출발부터 도착까지 최소 몇 걸음인지 구하는 문제예요.

# algorithms/dfs_bfs.py
def maze_shortest(maze, start, goal):
    rows, cols = len(maze), len(maze[0])
    sr, sc = start
    gr, gc = goal
    dist = {(sr, sc): 0}
    queue = deque([(sr, sc)])
    while queue:
        cr, cc = queue.popleft()
        if (cr, cc) == (gr, gc):        # 도착에 닿았다 — 지금이 최단
            return dist[(cr, cc)]
        for dr, dc in DIRECTIONS:
            nr, nc = cr + dr, cc + dc
            if 0 <= nr < rows and 0 <= nc < cols \
                    and maze[nr][nc] == 0 and (nr, nc) not in dist:
                dist[(nr, nc)] = dist[(cr, cc)] + 1
                queue.append((nr, nc))
    return -1                           # 큐가 비도록 못 닿았다 = 길이 막힘

격자 BFS에 거리 기록을 얹고, 상하좌우로 번지며 도착 칸에 처음 닿는 순간의 걸음 수를 돌려줍니다. 끝내 큐가 비도록 도착에 못 닿으면 길이 막힌 것이니 -1을 반환해요.

 미로 최단거리 — 0은 길, 1은 벽. (0,0)→(4,4)

   S 0 1 0 0       S = 출발(0,0)
   1 0 1 0 1       G = 도착(4,4)
   0 0 0 0 0       상하좌우로 BFS 물결을 퍼뜨려
   0 1 1 1 0       처음 G에 닿는 걸음 수를 센다
   0 0 0 1 G       최단 = 8걸음

maze_shortest(maze, (0,0), (4,4))는 8을 돌려줍니다. 출발에서 도착까지 가로 4칸·세로 4칸을 움직여야 하니 최소 8걸음인데, 우회 없이 곧장 갈 수 있는 길이 뚫려 있어 딱 그 8걸음에 닿아요.

한 가지 선을 그어 둡니다. BFS의 이 최단 경로는 "모든 간선의 걸음값이 1로 똑같은" 가중치 없는 그래프에서만 성립해요. 만약 간선마다 거리가 다르면(도로마다 길이가 다르듯) BFS로는 안 되고, 우선순위 큐(힙)를 쓰는 다익스트라가 필요합니다. 그건 C-2의 힙을 회수하는 F-1에서 만나요. 오늘은 "걸음값이 다 같으면 BFS가 곧 최단"까지만 확실히 잡아 둡시다.

💡 한 줄 정리

가중치 없는 그래프에서 BFS는 한 걸음씩 넓히므로, 어떤 정점에 처음 닿은 순간이 곧 최단 거리다. 방문 표시 대신 거리를 기록하면 최단 경로 길이가 나온다. 미로 최단거리가 대표 유형이고, 간선 값이 제각각이면 다익스트라(F-1)로 넘어간다.

Step 8: 정리 — DFS냐 BFS냐, 무엇을 언제

오늘 두 걸음걸이를 다 익혔으니, 마지막으로 "어떤 문제에 무엇을 고를까"를 정리합시다. 코딩테스트에서 그래프 문제를 만나면 가장 먼저 던질 질문이 바로 이거예요.

가장 강력한 기준은 최단 경로입니다. 가중치 없는 그래프에서 "최소 몇 걸음"을 물으면 거의 자동으로 BFS예요. DFS는 처음 닿은 게 최단이라는 보장이 없으니까요. 반대로 "경로가 존재하는가", "모든 경로를 다 만들어 보라", "백트래킹으로 조건을 만족하는 경우를 찾으라" 같은 문제는 DFS가 자연스럽습니다.

 DFS vs BFS — 언제 무엇을

빅오는 둘 다 O(V+E)로 같습니다. 격자면 O(H×W)죠. 그러니 선택은 속도가 아니라 "무엇을 구하느냐"로 갈립니다. 최단 거리면 BFS, 모든 경우를 훑거나 되돌리며 조건을 찾으면 DFS. 이 한 줄만 쥐고 있어도 코테 그래프 문제의 절반은 접근이 잡혀요.

코테 빈출 유형과 짝지어 두면 이렇습니다.

• 미로 최단거리, 토마토(며칠이면 다 익나), 숨바꼭질 → BFS(최단 거리)
• 섬의 개수, 단지번호붙이기, 연결 요소 → DFS/BFS 둘 다(덩어리 세기)
• N과 M, 알파벳 경로 최댓값, 백트래킹류 → DFS(완전탐색·되돌리기)

오늘 짠 일곱 함수 — dfs_recursive, dfs_stack, bfs, count_components, count_islands, bfs_distances, maze_shortest — 가 이 유형들의 뼈대입니다. 코드베이스 algorithms/dfs_bfs.py에 전부 들어 있으니, 문제를 만나면 이 골격을 꺼내 조금씩 변형해 쓰세요.

💡 한 줄 정리

선택 기준은 속도가 아니라 목적이다. 둘 다 O(V+E)라, 가중치 없는 최단 경로면 BFS, 모든 경로 탐색이나 백트래킹이면 DFS, 아주 깊은 그래프면 BFS(또는 스택 DFS)로 재귀 한계를 피한다. 연결 요소·섬 세기는 둘 다 통한다.

마무리

오늘은 C-3의 그래프와 지난 시간의 재귀를 합쳐, 그래프 위를 걷는 두 걸음걸이 DFS와 BFS를 익혔습니다. 방문 체크로 무한 루프를 막고, 깊게 파는 DFS와 넓게 퍼지는 BFS로 그래프와 격자를 훑고, 가중치 없는 최단 경로를 BFS로 구했어요. 코딩테스트 그래프 문제의 뼈대를 오늘 거의 다 세운 셈입니다.

오늘 배운 핵심 세 가지

• 💡 하나 — 탐색의 심장은 방문 체크(visited)다. 그래프엔 사이클이 있어 방문 표시를 안 하면 같은 정점을 오가며 무한히 돈다. DFS(스택/재귀)와 BFS(큐)는 방문 순서만 다를 뿐, 둘 다 이 visited 위에서 O(V+E)에 돈다.
• 💡 둘 — DFS는 깊게, BFS는 넓게. DFS는 한 길로 끝까지 파고들었다 되돌아오며(재귀 호출 스택), BFS는 가까운 겹부터 물결처럼 퍼진다(큐). 격자는 칸이 정점·상하좌우가 간선인 그래프라, 방향 델타로 이웃을 찾아 섬의 개수 같은 문제를 푼다.
• 💡 셋 — 가중치 없는 최단 경로는 BFS가 공짜로 준다. BFS는 한 걸음씩 넓히니 처음 닿은 순간이 곧 최단 거리다. 미로 최단거리가 대표 유형이고, 간선 값이 제각각이면 힙을 쓰는 다익스트라로 넘어간다.

돌아보면 오늘의 한 줄기는 "방문 체크 → DFS·BFS → 최단 경로"였어요. 두 탐색은 그래프 알고리즘의 기본기라, 앞으로 배울 고급 그래프가 전부 이 위에 섭니다.

다음 시간 예고

다음 시간(E-3)엔 "문제를 푸는 다섯 사고법"의 세 번째와 네 번째, 그리디(greedy)와 분할정복(divide and conquer)을 만납니다. 그리디는 매 순간 눈앞의 최선을 고르는 전략이에요 — 거스름돈을 줄 때 큰 동전부터 집는 그 직관이죠. 다만 "눈앞의 최선"이 정말 전체의 최선인지 따져 보는 게 핵심입니다. 분할정복은 문제를 반으로 쪼개 정복하는 방식인데, D-1에서 배운 병합 정렬·퀵 정렬이 바로 그 대표 사례라 반갑게 회수할 거예요. 오늘의 "다 뒤지는" 탐색과 달리, 다음 시간엔 "영리하게 고르고 쪼개는" 전략으로 넘어갑니다.

과제

오늘 배운 DFS·BFS와 격자 탐색을 손에 붙이는 문제들입니다. 코드베이스 algorithms/dfs_bfs.py의 함수를 가져다 쓰거나 직접 짜서 풀어 보세요. 각 문제의 시간·공간 복잡도를 빅오로 함께 적는 걸 잊지 마세요.

[기초] 도달 가능한 정점의 개수 세기

인접 리스트 그래프 graph와 시작 정점 start가 주어질 때, start에서 갈 수 있는(도달 가능한) 정점의 개수를 세는 count_reachable(graph, start)을 작성하세요. 시작 정점 자신도 포함합니다. 예를 들어 Step 1의 그래프에서 count_reachable(g, 0)은 6(모든 정점에 닿음), count_reachable({0:[1], 1:[0], 2:[]}, 0)은 2(0과 1만)입니다.

• DFS든 BFS든 상관없어요. 오늘 짠 dfs_recursive나 bfs가 돌려주는 방문 순서 목록의 길이가 곧 답입니다.
• 방문 체크가 없으면 어떤 일이 벌어지는지 한 줄로 적어 보세요(사이클이 있는 그래프에서).
• 이 탐색의 시간·공간 복잡도를 빅오로 적으세요.

[응용] 두 정점 사이 최단 거리

인접 리스트 그래프 graph와 두 정점 start, target이 주어질 때, start에서 target까지의 최단 거리(간선 수)를 구하는 shortest_hops(graph, start, target)을 BFS로 작성하세요. 닿을 수 없으면 -1을 반환합니다. 예를 들어 Step 1의 그래프에서 shortest_hops(g, 0, 5)는 3, shortest_hops(g, 0, 0)은 0입니다.

• 왜 이 문제는 DFS가 아니라 BFS여야 하는지 생각해 보세요(Step 7의 논리).
• Step 7의 bfs_distances를 응용하면 거의 그대로 풀립니다. 도착에 닿는 순간 멈추도록 짜면 더 효율적이에요.
• "친구의 친구는 몇 다리 건너 닿나" 같은 관계망 거리 문제가 이 골격입니다.

[심화] 미로 최단 경로 되짚기

Step 7의 maze_shortest는 최단 걸음 수만 돌려줬습니다. 이번엔 실제로 어떤 칸들을 밟아 도착했는지 그 경로를 좌표 목록으로 돌려주는 maze_path(maze, start, goal)을 작성하세요. 닿을 수 없으면 빈 목록을 반환합니다. 반환된 경로는 start로 시작해 goal로 끝나야 합니다.

• BFS로 번질 때 각 칸에 "어디서 왔는지(직전 칸)"를 함께 기록해 두세요. 도착에 닿으면 그 기록을 거꾸로 따라가며 경로를 복원합니다.
• 거꾸로 복원한 경로는 goal → start 순이니, 마지막에 뒤집어 start → goal로 만드세요.
• 이 "직전 칸 기록 → 거꾸로 복원" 기법은 최단 경로 자체를 요구하는 코테 문제에서 자주 씁니다. 시간 복잡도가 여전히 O(H×W)인지 확인하세요.

생각해볼 주제

1. DFS를 재귀로 짤까, 스택으로 짤까

오늘 DFS를 재귀 버전과 명시적 스택 버전 둘로 짰습니다. 재귀는 짧고 점화식이 그대로 드러나 읽기 좋지만 깊이 한계(약 1000)가 있고, 스택 버전은 깊이 걱정이 없지만 코드가 조금 길고 이웃을 역순으로 쌓는 등 손이 더 갑니다. 코딩테스트에서 그래프나 격자 문제를 만났을 때, 언제 재귀를 고르고 언제 스택으로 바꿀지 그 판단 기준을 정리해 보세요. 입력 크기(정점 수·격자 크기)와 "깊어질 수 있는 최악의 형태"를 어떻게 가늠할지, 그리고 sys.setrecursionlimit이 이 선택에 어떻게 끼어드는지 함께 생각해 보세요.

2. 최단 경로인데 왜 BFS는 되고 DFS는 안 될까

"가중치 없는 최단 경로는 BFS"라고 배웠습니다. 그런데 DFS도 모든 경로를 다 뒤지면 최단을 찾을 수 있는데, 왜 굳이 BFS를 정답이라 부를까요? 이 질문의 답은 "BFS가 처음 닿는 순간 그게 최단임이 보장된다"는 데 있습니다. 왜 그 보장이 성립하는지(거리별 겹으로 퍼진다는 성질), 그리고 DFS로 최단을 구하려 하면 왜 완전탐색으로 번져 비효율적이 되는지를 엮어 설명해 보세요. 나아가 만약 간선마다 걸음값이 다르면(가중치 그래프) 이 BFS의 보장이 왜 깨지는지도 함께 짚어 보면, 다음에 배울 다익스트라가 왜 필요한지가 자연스럽게 보일 거예요.

3. 격자 문제를 그래프로 보는 관점의 힘

오늘 격자(2차원 배열)를 "칸이 정점, 상하좌우가 간선인 그래프"로 바라봤습니다. 인접 리스트를 따로 만들지 않고 좌표 계산만으로 이웃을 찾았죠. 이렇게 "겉보기엔 그래프가 아닌 문제를 그래프로 바꿔 보는" 관점은 코딩테스트에서 아주 강력한 무기입니다. 격자 말고도 그래프로 환원할 수 있는 문제들을 떠올려 보세요(예: 단어 변환 — 한 글자씩 바꿔 다른 단어로 가는 경로, 상태 전이 — 어떤 상태에서 다음 상태로의 이동). "무엇을 정점으로 보고 무엇을 간선으로 볼 것인가"를 정하는 순간 익숙한 DFS/BFS로 풀리는 문제가 얼마나 많은지, 그 관점의 전환이 주는 힘에 대해 생각해 보세요.