Breadth First Search, BFS
오늘은 BFS를 알아보자
BFS는 트리나 그래프를 방문 또는 탐색하는 방법이다.
탐색 방법
- 루트에서 시작한다.
- 자식 노드들을 [1]에 저장한다.
- [1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다.
- [2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다.
- 위의 과정을 반복한다.
- 모든 노드를 방문하면 탐색을 마친다.
그림을 보면, DFS는 갈림길에서 하나의 길로 들어서서 막다른 길이 나올 때까지 깊게 탐색을 하는 것을 볼 수 있고, BFS는 갈림길에 연결되어 있는 모든 길을 한번씩 탐색한 뒤 다시 연결되어 있는 모든 길을 넓게 탐색하는 것을 볼 수 있다.
코드 구현
- 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
- 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
- 해당 칸을 이전에 방문했다면 아무 것도 하지않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
- 큐가 빌 때 까지 2번을 반복
bfs(그래프 탐색)
from collections import deque
def bfs (graph, start, visited):
# 큐 구현을 위한 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
graph = [
[],
[2, 3],
[1, 8],
[1, 4, 5],
[3, 5],
[3, 4],
[7, 8],
[6, 8],
[2, 6, 7]
]
# 노드별로 방문 정보를 리스트로 표현
visited = [False] * 9
bfs(graph, 1, visited)
bfs(2차원배열)
from collections import deque
def bfs (graph, visited):
# 상하좌우 네 방향을 의미
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 큐 구현을 위한 deque 라이브러리 활용
queue = deque([(0,0)])
# 현재 노드를 방문 처리
visited[0][0] = True
# 큐가 완전히 빌 때까지 반복
while queue:
# 큐에 삽입된 순서대로 노드 하나 꺼내기
x,y = queue.popleft()
# 탐색 순서 출력
print(x,y, end = ' ')
# 현재 처리 중인 노드에서 방문하지 않은 인접 노드를 모두 큐에 삽입
for i in range(4):
if not (visited[i]):
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 and graph[nx][ny] == 'O':
visited[nx][ny] = True; #방문표시
queue.append((nx, ny))
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'],
]
# 노드별 방문 정보
visited = [[False] * len(graph[0]) for _ in range(len(graph))]
bfs(graph, visited)
'PS > DFS_BFS' 카테고리의 다른 글
[백준] 24481번, 24482번 : 알고리즘 수업 - 깊이 우선 탐색 3, 4 파이썬 (0) | 2024.06.22 |
---|---|
[백준] 24479번, 24480번 : 알고리즘 수업 - 깊이 우선 탐색 1, 2 파이썬 (0) | 2024.06.19 |
DFS(깊이우선탐색) python으로 구현 (0) | 2024.06.18 |
[백준] 14940번: 쉬운 최단거리 파이썬 (0) | 2024.04.03 |
[백준] 11724번: 연결 요소의 개수 파이썬 (0) | 2024.04.02 |