[DS&AL] 너비 우선 탐색 (BFS, Breadth-First Search) 정리

너비 우선 탐색 (BFS)에 대해 이해하려면, 먼저 그래프 탐색이 무엇인지를 알아야 합니다.

그래프 탐색

그래프 탐색 문제 (Graph Search)는 어떤 한 그래프와 해당 그래프의 시작 정점(Node, Vertex)이 주어졌을 때, 시작점에서 간선(Edge)를 타고 이동할 수 있는 모든 정점들을 찾아야 하는 문제를 말합니다. 이 그래프 탐색 문제의 대표적인 예시로는,

• DFS (Depth-First Search, DFS)
• BFS (Breath-First Search, BFS) 가 있습니다.

현재, 이 알고리즘 등을 제가 알기로는, KG(Knowledge Graph) 등에서 많이 활용하고 있습니다.

이 페이지에서는, BFS를 먼저 설명하겠습니다.

BFS (너비 우선 탐색)

BFS (너비 우선 탐색)은 그래프 탐색 알고리즘의 큰 유형 중 하나로서, 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘을 말합니다. 즉, 한 지점에서 출발해 가까운 모든 노드들을 먼저 방문한 뒤, 그 다음 단계에서 더 멀리 있는 노드들을 방문합니다.

BFS의 작동원리는 크게 다음과 같습니다.

• 탐색 시작 노드 정보를 큐에 삽입하고, 방문처리한다.
  • 방문처리 : 탐색된 노드를 재방문하지 않도록 구분하는 형식
• 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모든 큐에 삽입하고 방문처리한다.
• 앞의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

그림과 함께 설명드리면, 해당 이미지에서 노드 시작을 1로 설정한다면, 크게 다음의 작동원리를 가지고 있습니다.

• 시작 노드인 노드 1을 큐에 삽입하고 방문처리한다.
• 큐에서 노드 1을 꺼내고, 노드 1과 인접한 노드 2, 3을 방문처리한다.
• 노드 2와 인접한 노드 8을 방문처리한다.
• 이 과정을 계속 진행해서 마지막 7까지 방문한다. 이렇게 진행되면, 방문 순서는 1 -> 2 -> 3 -> 8 -> 4 -> 5 -> 6 -> 7의 순서대로 방문합니다.

BFS의 구현

BFS의 구현에는 크게 큐(Queue) 자료구조를 사용합니다. 큐에 대해 간단하게 설명드리면,

from collections import deque
queue = deque()

FIFO (First in, First out) 구조를 사용하며, 가까운 것부터 탐색하는 방법을 사용합니다.

또한, 방문처리를 하기 위해 set을 사용해서 같은 노드를 여러번 방문하지 않도록 합니다.

visited = set()
visited.add((y, x))

단, 여기서 주의해야 할 점은, (x, y)로 집어넣는 것이 아닌, (y, x) 형태로 많이 집어넣습니다. 2차원 배열의 경우는, 위에서 아래로 (y), 왼쪽에서 오른쪽으로 (x) 읽기 때문에, 코드에서는 자연스러움을 위해 보통 y를 먼저 사용합니다. 그렇기에, 인간의 눈에서는 좌표를 (x, y)형태로 지정하지만, 리스트의 경우 실제로 (y, x)의 형태로 저장됩니다.

그 이후에, BFS의 간단한 기본 구조를 설명드리면, 크게 다음의 원리로 이루어집니다.

def bfs(sy, sx):
    queue = deque()
    queue.append((sy, sx))
    visited.add((sy, sx))

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

        for dy, dx in directions:
            ny, nx = y + dy, x + dx
            if 이동 가능:
                queue.append((ny, nx))

여기서 지정할 변수는 sy, sx는 시작 위치입니다 (세로 위치, 가로 위치). 다음으로 queue를 사용해서 나중에 방문할 칸들을 담아둡니다.

다음으로, 처음 start 지점을 먼저 큐에 넣고, 동시에 방문표시를 진행하고, queue가 빌때까지 반복을 진행합니다.

• 반복 진행 과정에서 가장 먼저 들어온 칸 하나를 꺼내고, 이 칸이 현재 내가 서있는 위치가 됩니다.
• 2개 ~ 4개 방향으로 이동할 수 있는데, 좌표들을 바탕으로 한칸씩 이동한 좌표를 반복문을 이용해서 계산합니다.
• 조건에 따라 이동가능한 경우, 이동하고 큐에 추가하는 방식으로 지속적인 탐색이 이루어집니다.

BFS의 예시 코드를 샘플로 보면 다음과 같습니다.

from collections import deque

def bfs(start_x, start_y, graph):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    queue = deque([(start_x, start_y)])
    visited = set([(start_x, start_y)])

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

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < len(graph) and 0 <= ny < len(graph[0]):
                if (nx, ny) not in visited:
                    visited.add((nx, ny))
                    queue.append((nx, ny))
    return -1
    
def solution():
    graph = [
        ['O', 'O', 'O', 'O', 'O', 'X'],
        ['O', 'O', 'O', 'O', 'X', 'O'],
        ['O', 'O', 'O', 'X', 'O', 'O'],
        ['O', 'O', 'X', 'O', 'O', 'O'],
        ['X', 'O', 'O', 'O', 'O', 'O'],
    ]
    bfs(0, 0, graph)
  

BFS의 문제 유형

BFS의 문제 유형은 크게 4가지로 구분됩니다.

1. 기본 순회 문제

현재 노드를 기준으로 이동할 수 있는 모든 노드를 탐색하는 문제입니다. “갈 수 있는 곳은 전부 탐색”을 목표로, 순서나 거리는 크게 중요하지 않습니다.

이 방법의 특징으로는 최단 거리를 계산하는 것이 아닌, 방문 했는지, 하지 않았는지 여부만 중요합니다. 이 문제는 DFS/BFS 두 케이스로 모두 풀 수 있지만, 보통 BFS로 푸는 경우가 더 간단합니다.

이 문제의 대표적인 예시가 백준 21736, 헌내기는 친구가 필요해 문제입니다. 또다른 기본 순회 문제의 형태는 미로에서 갈 수 있는 칸의 개수를 세거나, 특정 위치에서 도달 가능한 모든 위치 탐색 문제가 있습니다.

기본 순회 문제의 예시 코드는 다음과 같습니다.

from collections import deque

def bfs(start_row, start_col, graph):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    rows, cols = len(graph), len(graph[0])
    
    queue = deque([(start_row, start_col)])
    visited = set([(start_row, start_col)])
    
    while queue:
        row, col = queue.popleft()
    
        # 응용 포인트1: 문제에서 제시하는 종료 조건
        if row == 'T' and col == 'T':
            return row, col
    
        for i in range(4):
            next_row = row + dx[i]
            next_col = col + dy[i]
            
            if 0 <= next_row < rows and 0 <= next_col < cols:
                if (next_row, next_col) not in visited:
                    # 응용 포인트2: 문제에서 제시하는 추가 이동 조건
                    if graph[next_row][next_col] != 'X':
                        visited.add((next_row, next_col))
                        queue.append((next_row, next_col))
    return -1

2. 최단 경로 문제

특정 두 노드 사이의 최단 경로를 탐색하는 문제입니다. 이 문제는, BFS의 가장 중요한 성질인 최단 거리 보장을 활용하는 문제로, 거리 배열에 대한 정보를 추가로 활용합니다.

기존 BFS에서 각 노드까지의 거리를 저장하는 방식을 차용합니다. 예시는 다음과 같습니다.

dist[ny][nx] = dist[y][x] + 1

이 문제의 대표적인 문제 예시는, 최소 이동 횟수로 미로 탈출, 숨바꼭질, 토마토가 며칠 후에 익는지 등의 문제 예시가 있습니다.

최단 경로 문제의 대표 예시 코드는 다음과 같습니다.

from collections import deque

def bfs_shortest_distance(start_node, end_node, graph):
    # 응용 포인트1: {노드: 거리}
    queue = deque([start_node])
    visited = set([start_node])
    dist = {start_node: 0}

    while queue:
        curr_node = queue.popleft()

        # 응용 포인트2: 문제에서 제시하는 종료 조건
        if curr_node == end_node:
            return dist[curr_node]

        for next_node in graph[curr_node]:
            if next_node not in visited:
                visited.add(next_node)
                queue.append(next_node)
                # 응용 포인트1: {다음노드: 현재거리 + 1}
                dist[next_node] = dist[curr_node] + 1

    return -1

def BFS(start_x, start_y, end_x, end_y, graph):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    n, m = len(graph), len(graph[0])

    # 응용 포인트1: (좌표x, 좌표y, 거리)
    visited = set([(start_x, start_y)])
    queue = deque([(start_x, start_y, 1)])

    while queue:
        x, y, dist = queue.popleft()

        # 응용 포인트2: 문제에서 제시하는 종료 조건
        if x == end_x and y == end_y:
            return dist

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m:
                if (nx, ny) not in visited:
                    # 응용 포인트3: 문제에서 제시하는 추가 이동 조건
                    if graph[nx][ny] == 1:
                        # 응용 포인트1: (다음좌표x, 다음좌표y, 현재거리 + 1)
                        visited.add((nx, ny))
                        queue.append((nx, ny, dist + 1))

    return -1

3. 연결 요소 문제

현재 노드를 기준으로 연결된 모든 노드를 탐색하는 문제입니다. 쉽게 말하면, 그래프에서 서로 연결된 컴포넌트의 개수나 크기를 구하는 문제입니다.

“몇 개의 영역이 존재하는가?”가 핵심으로, BFS를 한 번 호출했던 문제와는 다르게, 여러 번 호출하며, 방문하지 않은 노드를 발견할 때마다 새로운 BFS를 시작하는 방식입니다.

이 문제의 대표적인 문제 예시는 섬의 개수 확인하기, 단지 번호 붙이기, 안전 영역 등이 있습니다.

연결 요소 문제의 대표 예시 코드는 다음과 같습니다.

from collections import deque

def count_components(grid):
    n, m = len(grid), len(grid[0])
    visited = [[False]*m for _ in range(n)]
    directions = [(-1,0),(1,0),(0,-1),(0,1)]

    def bfs(sy, sx):
        q = deque()
        q.append((sy, sx))
        visited[sy][sx] = True

        while q:
            y, x = q.popleft()
            for dy, dx in directions:
                ny, nx = y + dy, x + dx
                if 0 <= ny < n and 0 <= nx < m:
                    if not visited[ny][nx] and grid[ny][nx] == 1:
                        visited[ny][nx] = True
                        q.append((ny, nx))

    count = 0
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 1 and not visited[i][j]:
                bfs(i, j)
                count += 1

    return count

4. 플러드 필

그래프의 영역을 특정 색상으로 채우는, 일명 땅따먹기 문제입니다. 특정 위치에서 시작해, 같은 성질을 가지는 영역 전체를 채우거나 변경하는 문제입니다.

플러드 필은 연결 요소 문제의 응용 버전이라고 할 수 있으며, 방문하면서 색칠하거나 값 변경을 수행합니다.

플러드 필 문제의 대표 예시 코드는 다음과 같습니다.

from collections import deque

def flood_fill(grid, sy, sx, new_color):
    n, m = len(grid), len(grid[0])
    original_color = grid[sy][sx]
    if original_color == new_color:
        return grid

    q = deque()
    q.append((sy, sx))
    grid[sy][sx] = new_color

    directions = [(-1,0),(1,0),(0,-1),(0,1)]

    while q:
        y, x = q.popleft()
        for dy, dx in directions:
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                if grid[ny][nx] == original_color:
                    grid[ny][nx] = new_color
                    q.append((ny, nx))

    return grid

참조

[Python/코딩테스트] 코딩테스트 완전정복 ① - BFS 너비우선탐색

[이것이 코딩 테스트다 with Python] 19강 BFS 알고리즘