BFS 너비 우선 탐색

BFS 이론

BFS는 너비 우선탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.

BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 아래와 같다.

• 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
• 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않는 노드를 모두 큐에 삽입하고 방문처리한다.
• 2번의 과정을 수행할 수 없을때 까지 반복한다.

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

 

 

기본 형태

from collections import deque

# BFS 함수 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    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

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

 

 

응용① - 기본 순회

 

ⓐ Graph Dictionary

BFS 알고리즘을 사용하여 주어진 그래프에서 시작 노드부터 탐색하고, 방문한 노드 순서대로 출력하는 코드이다.

# 방문할 수 있는 정점이 여러개일 경우, 작은 노드를 먼저 방문한다.

백준 - 1260

from collections import deque  # deque 모듈을 import합니다. 큐를 구현하기 위해 사용됩니다.
bfs_result = []  # BFS 결과를 저장하기 위한 리스트를 초기화합니다.

def bfs(start_node, graph):  # BFS 함수를 정의합니다.
    queue = deque([start_node])  # 시작 노드로 큐를 초기화합니다.
    visited = set([start_node])  # 시작 노드를 방문했다고 표시합니다.

    while queue:  # 큐가 빌 때까지 반복합니다.
        curr_node = queue.popleft()  # 큐에서 노드를 하나 꺼냅니다.
        bfs_result.append(curr_node)  # 꺼낸 노드를 BFS 결과 리스트에 추가합니다.
        
        for next_node in graph[curr_node]:  # 현재 노드의 이웃 노드들에 대해 반복합니다.
            if next_node not in visited:  # 이웃 노드가 방문되지 않았다면
                visited.add(next_node)  # 방문했다고 표시하고
                queue.append(next_node)  # 큐에 추가합니다.
                
n, m, v = map(int, input().split())  # 노드의 수, 간선의 수, 시작 노드를 입력받습니다.

gragh = [[] for _ in range(n+1)]  # 그래프를 표현하기 위한 리스트를 초기화합니다.

for i in range(m):  # 간선 정보를 입력받고 그래프를 구성합니다.
    input_x, input_y = map(int, input().split())
    gragh[input_x].append(input_y) 
    gragh[input_y].append(input_x) 

for i in range(n+1):  # 각 노드의 이웃 노드들을 오름차순으로 정렬합니다.
    gragh[i].sort()

bfs(v, gragh)  # 시작 노드와 그래프를 이용하여 BFS를 수행합니다.
print(*bfs_result)  # BFS 결과를 출력합니다.

 

 

ⓑ Graph 2D Array

 

응용② - 최단경로, 최단거리

 

ⓐ Graph Dictionary를 이용한 최단 경로

 

 

ⓑ Graph Dictionary를 이용한 최단 거리

시작점에서 BFS를 사용하여 도착점까지의 최단 거리를 탐색하고 출력하는 코드이다.

백준 - 2178

from collections import deque  # deque 모듈을 import합니다. 큐를 구현하기 위해 사용됩니다.

n ,m = map(int, input().split())  # 그래프의 크기를 입력받습니다.
graph = []  # 그래프를 저장할 리스트를 초기화합니다.

for i in range(n):  # 그래프 정보를 입력받습니다.
    graph.append(list(map(int, input())))

dx = [-1, 1, 0, 0]  # 이동할 수 있는 방향을 표현하는 리스트입니다.
dy = [0, 0, 1, -1]

def bfs(start_x, start_y, graph):  # BFS 함수를 정의합니다.
    queue = deque([(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 < n and 0 <= ny < m and graph[nx][ny] == 1:  # 범위 내에 있고, 갈 수 있는 곳이라면
                    queue.append((nx, ny))  # 큐에 추가합니다.
                    graph[nx][ny] = graph[x][y] + 1  # 이동 거리를 갱신합니다.
    return graph[n-1][m-1]  # 도착점까지의 최단 거리를 반환합니다.

print(bfs(0, 0, graph))  # 시작점에서 BFS를 시작하여 최단 거리를 출력합니다.

 

 

ⓒ Graph 2D Array를 이용한 최단 경로

 

 

ⓓ Graph 2D Array를 이용한 최단 거리

 

 

 

반응형

응용③ - 연결 요소

 

ⓐ Graph Dictionary를 이용한 연결 요소 찾기

BFS를 사용하여 각 연결 요소를 탐색하여 방문한 노드의 수를 세어 연결 요소의 크기를 구하는 코드이다.

백준 - 2606

from collections import deque  # deque 모듈을 import합니다. 큐를 구현하기 위해 사용됩니다.

n = int(input())  # 노드의 수를 입력받습니다.
line = int(input())  # 간선의 수를 입력받습니다.
graph = [[] for _ in range(n+1)]  # 그래프를 표현하기 위한 리스트를 초기화합니다.

for i in range(line):  # 간선 정보를 입력받고 그래프를 구성합니다.
    com1, com2 = map(int, input().split())
    graph[com1].append(com2)
    graph[com2].append(com1)

def bfs(start_node, grahp):  # BFS 함수를 정의합니다.
    queue = deque([start_node])  # 시작 노드로 큐를 초기화합니다.
    visited = set([start_node])  # 시작 노드를 방문했다고 표시합니다.

    while queue:  # 큐가 빌 때까지 반복합니다.
        curr_node = queue.popleft()  # 큐에서 노드를 하나 꺼냅니다.

        for next_node in grahp[curr_node]:  # 현재 노드의 이웃 노드들에 대해 반복합니다.
            if next_node not in visited:  # 이웃 노드가 방문되지 않았다면
                visited.add(next_node)  # 방문했다고 표시하고
                queue.append(next_node)  # 큐에 추가합니다.

    return len(visited) - 1  # 방문한 노드의 수에서 시작 노드는 제외하고 반환합니다.

print(bfs(1, graph))  # 시작 노드를 기준으로 BFS를 수행하고, 연결 요소의 크기를 출력합니다.

 

ⓑ Graph 2D Array를 이용한 연결 요소 찾기

 

 

응용④ - 플러드 필 (ex. 땅따먹기)

 

ⓐ Graph Dictionary를 이용하여 다른 색 구분하기

 

 

ⓑ Graph 2D Array를 이용하여 다른 색 구분하기

그래프에서 서로 다른 색(구분된 영역)을 BFS를 통해 찾고, 각 영역의 크기를 출력하는 코드이다.

백준 - 2667

from collections import deque  # deque 모듈을 import합니다. 큐를 구현하기 위해 사용됩니다.

n = int(input())  # 그래프의 크기를 입력받습니다.
graph = [[] for _ in range(n+1)]  # 그래프를 표현하기 위한 2D 배열을 초기화합니다.

for i in range(n):  # 그래프 정보를 입력받습니다.
    graph[i] = list(map(int, input()))

dx = [0, -1, 1, 0, 0]  # 상하좌우, 제자리를 이동하기 위한 리스트입니다.
dy = [0, 0, 0, 1, -1]

def bfs(x, y, graph):  # BFS 함수를 정의합니다.
    queue = deque([(x, y)])  # 시작 좌표를 큐에 넣습니다.

    while queue:  # 큐가 빌 때까지 반복합니다.
        x, y = queue.popleft()  # 큐에서 좌표를 하나 꺼냅니다.

        for i in range(5):  # 현재 위치에서 상하좌우, 제자리로 이동합니다.
            nx = x + dx[i]  # 다음 좌표를 계산합니다.
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and graph[nx][ny]==1:  # 그래프 범위 내에 있고, 방문하지 않았다면
                graph[nx][ny] = 0  # 방문했다고 표시하고
                queue.append((nx, ny))  # 큐에 좌표를 추가합니다.
                
cnt = 0  # 영역의 수를 저장하기 위한 변수입니다.
result = []  # 각 영역의 크기를 저장하기 위한 리스트입니다.
for i in range(n):  # 모든 좌표에 대해 반복합니다.
    for j in range(n):
        if graph[i][j] == 1:  # 아직 방문하지 않은 좌표라면
            cnt += 1  # 새로운 영역을 시작하고
            result.append(0)  # 해당 영역의 크기를 저장할 공간을 할당합니다.
            bfs(i, j, graph)  # BFS를 사용하여 영역을 탐색합니다.

print(cnt)  # 구분된 영역의 수를 출력합니다.
result.sort()  # 각 영역의 크기를 정렬합니다.
for i in range(len(result)):  # 각 영역의 크기를 출력합니다.
    print(result[i])

 

 

 

Reference

Baekjoon Online Judge

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

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체