1. BFS의 핵심 작동 원리

1. 시작 노드를 큐에 넣고 방문 처리(Visited) 합니다.
2. 큐에서 노드를 하나 꺼냅니다 (popleft).
3. 꺼낸 노드와 인접한 노드들 중 아직 방문하지 않은 노드를 모두 큐에 넣고 방문 처리합니다.
4. 큐가 빌 때까지 2~3번 과정을 반복합니다.

2. 파이썬 BFS 템플릿 코드 (1차원 그래프)

가장 기본적인 인접 리스트 형태의 BFS 탐색 예제입니다. 이 코드 구조를 이해하면 다양한 그래프 문제에 응용할 수 있습니다.

pythonfrom collections import deque

# 1. 그래프 정보 (각 노드가 연결된 인접 노드 리스트)
graph = [
    [],        # 0번은 편의상 비움
    [2, 3, 8], # 1번 노드 인접
    [1, 7],    # 2번 노드 인접
    [1, 4, 5], # 3번 노드 인접
    [3, 5],    # 4번 노드 인접
    [3, 4],    # 5번 노드 인접
    [7],       # 6번 노드 인접
    [2, 6, 8], # 7번 노드 인접
    [1, 7]     # 8번 노드 인접
]

# 2. 방문 여부 리스트
visited = [False] * 9

# 3. BFS 함수 정의
def bfs(start):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        print(v, end=' ')
        
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 실행 예시
bfs(1)

1 2 3 8 7 4 5 6

3. 실전 응용: 2차원 배열 BFS (미로 찾기)

백준이나 프로그래머스에서는 2차원 격자(Grid) 형태에서의 BFS 탐색이 자주 등장합니다.

pythonfrom collections import deque

# 1. 맵 정보 (1: 이동 가능, 0: 벽)
n, m = 4, 5
graph = [
    [1, 0, 1, 1, 1],
    [1, 0, 1, 0, 1],
    [1, 1, 1, 0, 1],
    [0, 0, 0, 0, 1]
]

# 2. 이동 방향 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            # 범위를 벗어나거나 벽(0)이면 무시
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == 0:
                continue
            
            # 처음 방문하는 곳이면 거리 갱신
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
                
    # 도착지까지의 최단 거리 반환
    return graph[n-1][m-1]

# (0, 0)에서 출발
print(bfs(0, 0))  # 출력: 최소 이동 칸 수

🌟 핵심 포인트: graph 배열 자체에 현재까지의 거리 값을 누적시키는 방식으로 최단 거리 탐색을 구현할 수 있습니다.