[Algorithm]DFS/BFS(3) - BFS
지난 포스팅에선 DFS에 대해 설명하였다. 그럼 이번 포스팅에서는 BFS에 대해 알아보자.
📌BFS
너비 우선 탐색 알고리즘은, 가까운 노드부터 탐색하는 알고리즘이다. DFS는 최대한 멀리 있는 노드를 우선 탐색한다는 방식이였다면, BFS는 그 반대이다. BFS를 구현 할 때에는 선입선출 방식인 큐를 이용하는것이 정석이다. 인접한 노드들을 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온것이 먼저 나가게 되며, 가까운 노드부터 탐색을 진행하게 된다. 알고리즘의 로직은 다음과 같다.
1. 탐색 시작 노드를 큐에 넣고 방문 처리한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드중, 방문하지 않은 노드들을 모두 큐에 삽입후 방문 처리를 한다.
3. 2번의 과정을 더 이상 반복 할 수 없을 때까지 반복한다.
너비 우선 탐색 알고리즘은 큐 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로 구현함에 있어 deque라이브러리를 이용하는것이 좋으며, 탐색을 수행함에 있어 O(N)의 시간이 소요된다. 일반적인 경우 실제 수행 시간은 DFS보다 좋다는 것만 기억하자.
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)
실행결과 : 1 2 3 8 7 4 5 6
이제 DFS/BFS에 대해 간단히 알고 넘어갔으므로 다음은 예제들을 보며 더 깊게 이해해 보자.
📚예제 1) 음료수 얼려 먹기(DFS)
이 문제는 dfs로 해결 할 수 있다. 앞에서 배운대로 얼음을 얼릴 수 있는 공간이 상 하 좌 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링 할 수 있다. 예를들어 다음과 같이 3x3크기의 얼음 틀이 있다고 가정 해보자.
001
010
101
다음 그래프와 같이 모델링 될 수 있다. DFS를 사용하는 로직은 다음과 같다.
1. 특정한 지점의 주변 상,하,좌,우를 살핀 뒤, 주변 값중 값이 '0'이면서 아직 방문하지 않은 노드를 방문한다.
2. 방문한 지점에서 다시 상,하,좌,우를 살피면서 방문을 진행하면, 연결된 모든 지점을 방문 할 수 있다.
3. 1~2번의 과정을 모든 노드에 반복하며 방문하지 않은 지점의 수를 센다.
# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
graph.append(list(map(int, input().split())))
# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문
def dfs(x, y):
# 주어진 범위를 벗어나는 경우에는 즉시 종료
if x <= -1 or x >= n or y <= -1 or y >= m:
return False
# 현재 노드를 아직 방문하지 않았다면
if graph[x][y] == 0:
# 해당 노드 방문 처리
graph[x][y] = 1
# 상, 하, 좌, 우의 위치도 모두 재귀적으로 호출
dfs(x - 1, y)
dfs(x + 1, y)
dfs(x, y - 1)
dfs(x, y + 1)
return True
return False
# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
for j in range(m):
# 현재 위치에서 DFS 수행
if dfs(i, j) == True:
result += 1
print(result) # 정답 출력
📚예제 2) 미로 탈출(BFS) - 최단경로 탐색
이 문제는 BFS를 이용했을때 시작 노드부터 가장 인접한 노드들을 탐색하므로 매우 효과적이다. 그러므로 (1,1)을 기점으로 BFS를 실행하여 모든 노드의 값을 거리 정보로 넣어주면 된다. 특정 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 리스트에 넣는다. 예를들어 다음과 같은 3x3의 미로가 주어졌다고 가정해보자.
110
010
011
from collections import deque
# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
graph.append(list(map(int, input().split())))
# 이동할 네 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# BFS 소스코드 구현
def bfs(x, y):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
queue.append((x, y))
# 큐가 빌 때까지 반복
while queue:
x, y = queue.popleft()
# 현재 위치에서 네 방향으로의 위치 확인
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 미로 찾기 공간을 벗어난 경우 무시
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
# 벽인 경우 무시
if graph[nx][ny] == 0:
continue
# 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
# 가장 오른쪽 아래까지의 최단 거리 반환
return graph[n - 1][m - 1]
# BFS를 수행한 결과 출력
print(bfs(0, 0))