728x90
반응형
너비 우선 탐색(BFS)
그래프 순회의 완전 탐색 개념을 적용한 알고리즘 중 하나인 너비 우선 탐색(BFS, Breadth-First Search)에 대해 알아보겠다.
1. 그래프 순회 (Graph Traversal)
그래프 순회에 완전 탐색의 개념을 적용하면 모든 정점을 체계적으로 방문할 수 있는 두 가지 중요한 방법을 얻을 수 있다.
이것은 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이다.
▶ 그래프 탐색: 하나의 정점으로부터 시작하여 차례대로 모든 정점을 한 번씩 방문하는 것
구현
- DFS: 스택 or 재귀함수로 구현
- BFS: 큐를 이용하여 구현
예시
- 특정 도시에서 다른 도시로 갈 수 있는지 없는지
- 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지
2. 너비 우선 탐색(BFS, Breadth-First Search)의 개념 및 특성
📌 너비 우선 탐색의 개념
- 루트 노드(혹은 다른 임의의 노드)에서 시작해 인접한 노드를 먼저 탐색하는 방법
- 레벨이 낮은 노드들부터 방문하는 순회 방법
- 즉, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문한다.
- 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것
📌 사용하는 경우
최단 거리나 최단 시간 등 목표 상태에서 도달할 수 있는 가장 빠른 경로 탐색
📌 특성
탐색 공간의 깊이 제약이 없는 편이지만 공간복잡도가 크다
큐(Queue)를 사용하여 구현한다 : 큐가 탐색 공간을 나타내고 큐에 다음 탐색할 것들을 추가하는 방식
3. 너비 우선 탐색(BFS) 구현
📌 구현 방법
- BFS 알고리즘은 Queue에서 정점을 뽑아서 정점을 순회한다.
- 해당 정점을 순회 후에 해당 정점의 인접 정점 중 방문하지 않은 정점을 모두 큐에 넣어준다. (순서 무관)
큐(Queue)
FIFO(First In First Out) 구조이다: 먼저 들어온 것 먼저 나간다.
📌 파이썬 BFS 구현 코드
- graph: 순회할 그래프
- start: 시작할 정점
- visited: 방문한 정점
- nbr: 해당 정점(v)의 인접 정점들
import queue
def bfs(graph, start):
visited = { start }
que = queue.Queue()
que.put(start) # 큐에 시작정점 추가
while not que.empty():
v = que.get() # 큐에서 하나 꺼내기
print(v, end=' ')
nbr = graph[v] - visited # 꺼낸 노드와 인접한 노드들 리스트
# 인접 노드들 순회
for u in nbr:
visited.add(u) # 방문한 노드 체크
que.put(u) # 큐에 추가
📌 복잡도
- 인접 리스트 표현: O(n + e)
- 인접 행렬 표현: O(n^2)
2차원 배열에서 BFS 탐색하는 경우
# N×N 2차원 배열
dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)
# 방문한 노드일 경우 True / 방문하지 않은 노드일 경우 False
visited = [[False for _ in range(N)] for _ in range(N)]
def BFS(r, c):
q = deque() # 탐색해야 하는 노드들을 담는 큐
# 탐색을 시작하는 노드 (r, c)
q.append((r, c))
visited[r][c] = True
route = [] # 탐색 경로 저장
route.append((r, c))
# 큐에 들어가 있는 노드가 없을 때까지(탐색이 완료될 때까지) 반복
while q:
# 현재 탐색 중인 노드 (y, x)
y, x = q.popleft()
for i in range(4):
# 인접 노드 (ny, nx)
ny = y + dy[i]
nx = x + dx[i]
# 조건문을 통해 탐색 가능한 노드인지 확인
if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx]:
visited[ny][nx] = True
q.append((ny, nx)) # 인접한 노드를 전부 탐색하기 위해 큐에 다시 append
route.append((ny, nx))
return route
📌 인접리스트(딕셔너리와 집합)로 이루어진 그래프 mygraph 입력받기
mygraph = dict()
n = int(input())
for i in range(n):
e1, e2 = input().split()[:2]
mygraph[e1] = mygraph.setdefault(e1, set())|{e2}
mygraph[e2] = mygraph.setdefault(e2, set())|{e1}
참고 자료
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
https://bubblebubble.tistory.com/59
728x90
반응형