기쁘달

BFS (너비 우선 탐색)

12 min read

개념

Breadth-First Search - 너비 우선 탐색

가까운 노드부터 레벨별로 탐색하는 알고리즘

시간복잡도

표현 방법시간복잡도
인접 리스트O(V + E)
인접 행렬O(V²)

V: 정점 수, E: 간선 수

특징

동작 방식

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

탐색 순서: 1 → 2 → 3 → 4 → 5
(레벨별로 탐색)

장점

  • 최단 경로 보장: 가중치 없는 그래프에서 최단 거리
  • 레벨별 탐색: 단계적 처리 가능
  • 완전성: 해가 있으면 반드시 찾음

단점

  • 메모리 사용 많음: 모든 레벨의 노드 저장
  • 구현 복잡: DFS보다 코드가 약간 김

구현 방법

1. 기본 BFS (큐 사용)

from collections import deque
 
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
 
    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')
 
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
 
# 테스트
graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1],
    4: [2],
    5: [2]
}
 
bfs(graph, 1)  # 1 2 3 4 5
 
# 시간복잡도: O(V + E)
# 공간복잡도: O(V)

2. 레벨별 BFS

def bfs_level(graph, start):
    visited = set([start])
    queue = deque([start])
    level = 0
 
    while queue:
        level_size = len(queue)
        print(f"Level {level}:", end=' ')
 
        for _ in range(level_size):
            vertex = queue.popleft()
            print(vertex, end=' ')
 
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
 
        print()  # 줄바꿈
        level += 1
 
# 테스트
bfs_level(graph, 1)
# Level 0: 1
# Level 1: 2 3
# Level 2: 4 5
 
# 시간복잡도: O(V + E)

3. 최단 거리 계산

def bfs_shortest_distance(graph, start):
    visited = set([start])
    queue = deque([(start, 0)])  # (노드, 거리)
    distances = {start: 0}
 
    while queue:
        vertex, dist = queue.popleft()
 
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                distances[neighbor] = dist + 1
                queue.append((neighbor, dist + 1))
 
    return distances
 
# 테스트
print(bfs_shortest_distance(graph, 1))
# {1: 0, 2: 1, 3: 1, 4: 2, 5: 2}

4. 최단 경로 추적

def bfs_shortest_path(graph, start, end):
    visited = set([start])
    queue = deque([[start]])  # 경로를 저장
 
    while queue:
        path = queue.popleft()
        vertex = path[-1]
 
        # 목표 도달
        if vertex == end:
            return path
 
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                new_path = path + [neighbor]
                queue.append(new_path)
 
    return None
 
# 테스트
print(bfs_shortest_path(graph, 1, 5))  # [1, 2, 5]
 
# 시간복잡도: O(V + E)
# 공간복잡도: O(V²) - 경로 저장

자주 나오는 문제 유형

1. 최단 거리 (가중치 없음)

문제: 시작점에서 모든 노드까지의 최단 거리

def shortest_distances(graph, start, n):
    distances = [-1] * n
    distances[start] = 0
    queue = deque([start])
 
    while queue:
        vertex = queue.popleft()
 
        for neighbor in graph[vertex]:
            if distances[neighbor] == -1:
                distances[neighbor] = distances[vertex] + 1
                queue.append(neighbor)
 
    return distances
 
# 테스트
graph = [
    [1, 2],     # 0
    [0, 3],     # 1
    [0, 3],     # 2
    [1, 2]      # 3
]
print(shortest_distances(graph, 0, 4))  # [0, 1, 1, 2]
 
# 시간복잡도: O(V + E)

핵심: BFS는 가중치 없는 그래프에서 최단 거리 보장

2. 미로 탈출 (최단 경로)

문제: 2D 그리드에서 시작점부터 도착점까지 최단 거리

from collections import deque
 
def shortest_path_grid(grid, start, end):
    rows, cols = len(grid), len(grid[0])
    sr, sc = start
    er, ec = end
 
    if grid[sr][sc] == 1 or grid[er][ec] == 1:
        return -1
 
    queue = deque([(sr, sc, 0)])  # (row, col, distance)
    visited = set([(sr, sc)])
 
    # 4방향
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
 
    while queue:
        r, c, dist = queue.popleft()
 
        # 도착
        if r == er and c == ec:
            return dist
 
        # 4방향 탐색
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
 
            if (0 <= nr < rows and 0 <= nc < cols and
                grid[nr][nc] == 0 and (nr, nc) not in visited):
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))
 
    return -1  # 경로 없음
 
# 테스트
grid = [
    [0, 0, 1, 0],
    [0, 0, 0, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0]
]
print(shortest_path_grid(grid, (0, 0), (3, 3)))  # 6
 
# 시간복잡도: O(rows × cols)

핵심: BFS는 먼저 도달한 것이 최단 경로

3. 토마토 (다중 시작점 BFS)

문제: 익은 토마토(1)가 인접한 토마토를 익히는 최소 일수

def ripen_tomatoes(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    unripe = 0
 
    # 모든 익은 토마토를 큐에 추가
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                queue.append((i, j, 0))
            elif grid[i][j] == 0:
                unripe += 1
 
    if unripe == 0:
        return 0
 
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    max_days = 0
 
    while queue:
        r, c, days = queue.popleft()
        max_days = max(max_days, days)
 
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
 
            if (0 <= nr < rows and 0 <= nc < cols and
                grid[nr][nc] == 0):
                grid[nr][nc] = 1
                unripe -= 1
                queue.append((nr, nc, days + 1))
 
    return max_days if unripe == 0 else -1
 
# 테스트
grid = [
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 0]
]
grid[0][0] = 1  # 익은 토마토
print(ripen_tomatoes(grid))  # 4
 
# 시간복잡도: O(rows × cols)

핵심: 다중 시작점 BFS - 모든 시작점을 큐에 넣고 시작

4. 뱀과 사다리 게임

문제: 주사위를 굴려 100번 칸에 도달하는 최소 횟수

def snakes_and_ladders(board):
    n = len(board)
    target = n * n
 
    # 보드 좌표를 1차원으로 변환
    def get_position(num):
        row = (num - 1) // n
        col = (num - 1) % n
        if row % 2 == 1:
            col = n - 1 - col
        return n - 1 - row, col
 
    queue = deque([(1, 0)])  # (위치, 굴린 횟수)
    visited = {1}
 
    while queue:
        pos, moves = queue.popleft()
 
        if pos == target:
            return moves
 
        # 주사위 1~6
        for i in range(1, 7):
            next_pos = pos + i
            if next_pos > target:
                break
 
            r, c = get_position(next_pos)
 
            # 뱀이나 사다리가 있으면
            if board[r][c] != -1:
                next_pos = board[r][c]
 
            if next_pos not in visited:
                visited.add(next_pos)
                queue.append((next_pos, moves + 1))
 
    return -1
 
# 시간복잡도: O(n²)

핵심: 상태 공간 탐색 - 각 위치를 노드로

5. 단어 변환 (Word Ladder)

문제: 한 글자씩 바꿔서 시작 단어를 끝 단어로 변환하는 최소 횟수

def word_ladder(begin_word, end_word, word_list):
    if end_word not in word_list:
        return 0
 
    word_set = set(word_list)
    queue = deque([(begin_word, 1)])
 
    while queue:
        word, length = queue.popleft()
 
        if word == end_word:
            return length
 
        # 한 글자씩 변경 시도
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + c + word[i+1:]
 
                if next_word in word_set:
                    word_set.remove(next_word)
                    queue.append((next_word, length + 1))
 
    return 0
 
# 테스트
print(word_ladder("hit", "cog", ["hot","dot","dog","lot","log","cog"]))
# 5 (hit → hot → dot → dog → cog)
 
# 시간복잡도: O(M² × N) - M: 단어 길이, N: 단어 개수

핵심: 각 단어를 노드로, 한 글자 차이를 간선으로

6. 나이트의 이동

문제: 체스판에서 나이트가 목표 위치까지 최소 이동 횟수

def knight_moves(start, end, n=8):
    if start == end:
        return 0
 
    # 나이트의 8방향 이동
    moves = [
        (-2, -1), (-1, -2), (1, -2), (2, -1),
        (2, 1), (1, 2), (-1, 2), (-2, 1)
    ]
 
    queue = deque([(start[0], start[1], 0)])
    visited = set([start])
 
    while queue:
        x, y, dist = queue.popleft()
 
        for dx, dy in moves:
            nx, ny = x + dx, y + dy
 
            if nx == end[0] and ny == end[1]:
                return dist + 1
 
            if (0 <= nx < n and 0 <= ny < n and
                (nx, ny) not in visited):
                visited.add((nx, ny))
                queue.append((nx, ny, dist + 1))
 
    return -1
 
# 테스트
print(knight_moves((0, 0), (7, 7), 8))  # 6
 
# 시간복잡도: O(n²)

핵심: 특수한 이동 규칙에도 BFS 적용 가능

추천 연습 문제

기초

중급

고급

핵심 요약

개념설명
탐색 방식레벨별로 가까운 노드부터
구현큐 사용 (deque)
시간복잡도O(V + E)
활용최단 거리, 레벨 탐색

BFS 템플릿

기본 템플릿

from collections import deque
 
def bfs(start):
    visited = set([start])
    queue = deque([start])
 
    while queue:
        vertex = queue.popleft()
 
        # 현재 노드 처리
        process(vertex)
 
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

최단 거리 템플릿

def bfs_distance(start, end):
    queue = deque([(start, 0)])
    visited = set([start])
 
    while queue:
        vertex, dist = queue.popleft()
 
        if vertex == end:
            return dist
 
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
 
    return -1

2D 그리드 템플릿

def bfs_grid(start_r, start_c):
    queue = deque([(start_r, start_c)])
    visited = set([(start_r, start_c)])
 
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
 
    while queue:
        r, c = queue.popleft()
 
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
 
            if (0 <= nr < rows and 0 <= nc < cols and
                (nr, nc) not in visited and grid[nr][nc] == target):
                visited.add((nr, nc))
                queue.append((nr, nc))

레벨별 처리 템플릿

def bfs_by_level(start):
    queue = deque([start])
    visited = set([start])
 
    while queue:
        level_size = len(queue)
 
        for _ in range(level_size):
            vertex = queue.popleft()
 
            # 현재 레벨 처리
            process(vertex)
 
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

DFS vs BFS

특성DFSBFS
자료구조스택 (재귀)큐
탐색 방식깊이 우선너비 우선
최단 경로보장 안 됨보장됨 (가중치 없을 때)
메모리O(h) - 높이O(w) - 너비
활용경로, 사이클, 위상 정렬최단 거리, 레벨 탐색
구현재귀로 간단큐로 반복

주의사항

1. deque 사용 필수

from collections import deque
 
# O(1)
queue = deque()
queue.append(x)
queue.popleft()
 
# list는 popleft가 O(n)으로 비효율적

2. 방문 체크 시점

# 올바른 방법: 큐에 넣을 때 방문 체크
if neighbor not in visited:
    visited.add(neighbor)  # 여기서 체크!
    queue.append(neighbor)
 
# 잘못된 방법: 큐에서 뺄 때 체크하면 중복 추가

3. 다중 시작점 BFS

# 모든 시작점을 먼저 큐에 추가
for i in range(n):
    if is_start(i):
        queue.append(i)
        visited.add(i)

4. 상태 공간 탐색

# 위치뿐 아니라 상태도 저장
queue.append((position, state))
visited.add((position, state))

최적화 기법

1. 양방향 BFS

# 시작점과 끝점에서 동시에 탐색
# 만나는 지점 찾기
# 시간복잡도: O(b^(d/2)) vs O(b^d)

2. 0-1 BFS

# 가중치가 0 또는 1일 때
# 0인 간선은 앞에, 1인 간선은 뒤에 추가
from collections import deque
 
queue = deque([start])
if weight == 0:
    queue.appendleft(next_node)
else:
    queue.append(next_node)

그래프 뷰

백링크