Hyundae's Note

BFS (Breadth-First Search) 정리

 
  • 2025년 12월 29일

BFS Search

BFS(Breadth-First Search)는 시작 정점(또는 칸) 에서 가까운 것부터(=레벨/거리 순서대로) 탐색을 진행하는 대표적인 그래프 탐색 알고리즘이다.
핵심 자료구조는 Queue(큐) 이며, 방문 여부를 저장하는 visited 배열과 함께 사용한다.

1. BFS가 유리한 상황

  • 최단 거리(최소 이동 횟수) 를 구해야 할 때
    (간선 가중치가 모두 동일한 그래프/격자에서, BFS는 방문 레벨이 곧 최단거리)
  • “한 번에 1칸/1간선씩 확장”하는 형태의 탐색 문제
    (미로, 격자 이동, 전파/확산, 단계별 상태 전이 등)

2. DFS와 BFS 차이 (감 잡기)

  • DFS: 한 방향으로 깊게 들어갔다가 막히면 되돌아옴 (스택/재귀)
  • BFS: 현재 거리에서 갈 수 있는 곳을 전부 본 뒤, 다음 거리로 넘어감 (큐)

방문 순서가 달라지고, 특히 최단거리 문제는 BFS가 정석인 경우가 많다.

3. 그래프에서 BFS

그래프 표현은 보통 둘 중 하나를 쓴다.

3.1 인접 행렬 (Adjacency Matrix)

  • graph[u][v] = 1이면 간선 존재
  • 정점 수가 작거나, 간선 존재 여부를 O(1)로 자주 확인해야 할 때 편함
  • 단점: 메모리 O(V^2)

BFS 흐름

  1. 시작 정점을 큐에 넣고 visited[start]=True
  2. 큐에서 하나 꺼내서(cur), cur과 연결된 정점들을 확인
  3. 아직 방문 안 한 정점을 큐에 넣고 방문 처리
  4. 큐가 빌 때까지 반복
from collections import deque

def bfs_matrix(graph, start):
    n = len(graph)  # 정점 개수
    visited = [False] * n
    q = deque([start])
    visited[start] = True

    order = []
    while q:
        cur = q.popleft()
        order.append(cur)

        for nxt in range(n):
            if graph[cur][nxt] and not visited[nxt]:
                visited[nxt] = True
                q.append(nxt)

    return order

중요: visited는 보통 “큐에 넣는 순간” True로 바꾼다.
그래야 같은 정점이 큐에 여러 번 들어가는 걸 방지한다.

3.2 인접 리스트 (Adjacency List)

  • graph[u] = [u와 연결된 정점들...]
  • 희소 그래프(간선이 적음)에 효율적
  • 시간/메모리 측면에서 코테에서 가장 흔함
from collections import deque

def bfs_list(graph, start):
    visited = [False] * len(graph)
    q = deque([start])
    visited[start] = True

    order = []
    while q:
        cur = q.popleft()
        order.append(cur)

        for nxt in graph[cur]:
            if not visited[nxt]:
                visited[nxt] = True
                q.append(nxt)

    return order

4. 격자(Grid)에서 BFS

격자 BFS는 “정점 = 칸”으로 보고, 상하좌우(또는 8방향) 이웃 칸으로 간선을 만든다고 생각하면 된다.

4.1 기본 템플릿

  • dx, dy로 이동 방향 정의
  • in_range(x, y)로 범위 체크
  • can_go(x, y)로 범위 + 미방문 + 장애물 아님 같은 조건을 한 번에 체크
from collections import deque

def bfs_grid(grid, sx, sy):
    n, m = len(grid), len(grid[0])
    visited = [[False]*m for _ in range(n)]
    dist = [[-1]*m for _ in range(n)]

    dxs = [1, -1, 0, 0]
    dys = [0, 0, 1, -1]

    def in_range(x, y):
        return 0 <= x < n and 0 <= y < m

    def can_go(x, y):
        return in_range(x, y) and (not visited[x][y]) and grid[x][y] != '#'

    q = deque()
    q.append((sx, sy))
    visited[sx][sy] = True
    dist[sx][sy] = 0

    while q:
        x, y = q.popleft()

        for dx, dy in zip(dxs, dys):
            nx, ny = x + dx, y + dy
            if can_go(nx, ny):
                visited[nx][ny] = True
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))

    return dist
  • grid[x][y] != '#' 부분은 문제에 맞게 바꿔서 사용
    (예: 0/1, 벽/길, 뱀/빈칸 등)

4.2 최단거리 포인트

  • BFS에서 어떤 칸을 처음 방문했을 때의 dist가 곧 최단거리
  • 따라서 방문 처리 시점(enqueue 시점)을 지키는 게 매우 중요

5. 시간 복잡도

  • 인접 리스트 그래프 BFS: O(V + E)
  • 격자 BFS: 칸 수가 N*M이면 O(N*M)
    (각 칸을 최대 한 번만 큐에 넣기 때문)

6. 실전 팁

  • 방문 처리: “꺼낼 때”가 아니라 넣을 때 체크하기
  • 좌표 문제는 x=row, y=col 규칙을 끝까지 일관되게
  • 최단거리만 필요하면 dist를 -1로 초기화하고, 방문과 함께 갱신하는 방식이 편함
  • “우선순위(작은 번호부터 방문)” 조건이 있으면
    • 그래프: 인접 리스트를 미리 정렬하거나, 입력이 정렬되어 있다는 가정 확인
    • 격자: 방향 순서(dx,dy)를 문제 조건대로 배치

7.예시

  1. 최단거리가 아니라 도착 가능 여부만 확인하는 경우
from collections import deque


n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]

# Please write your code here.

def bfs_grid(grid, sx, sy):
    n, m = len(grid), len(grid[0])
    visited = [[False] * m for _ in range(n)]
    dist = [[-1] * m for _ in range(n)]

    dxs = [1, -1, 0 , 0]
    dys = [0, 0, 1, -1]

    def in_range(x, y):
        return 0 <= x < n and 0 <= y < m

    def can_go(x, y):
        return in_range(x, y) and (not visited[x][y]) and grid[x][y] != 0

    q = deque()
    q.append((sx, sy))
    visited[sx][sy] = True
    dist[sx][sy] = 0

    while q:
        x, y = q.popleft()

        #도착하면 바로 성공
        if(x, y) == (n - 1, m - 1):
            return 1

        for dx, dy in zip(dxs, dys):
            nx, ny = x + dx, y + dy
            if can_go(nx, ny):
                visited[nx][ny] = True
                q.append((nx, ny))

    return 0

print(bfs_grid(a, 0, 0))
검색