BFS(너비우선탐색)
BFS는 대표적인 탐색 알고리즘 중 하나이다.
쉽게 말하자면 가까운 노드부터 탐색하는 알고리즘으로 주로 큐를 이용한다.
root와 가까운 node부터 찾기 때문에 최단거리 탐색, SNS 친구찾기 등에 유용하다.
메모리를 많이 쓰는 대신 DFS보다 빠른 편이다.
탐색이란
많은 양의 데이터 중에서 원하는 데이터를 찾는 과정. 그래프, 트리 등의 자료구조 안에서 탐색을 주로 한다.
대표적인 탐색 알고리즘이 바로 BFS와 DFS이다.
이 알고리즘들을 제대로 이해하려면 스택과 큐, 재귀 함수에 대한 이해도가 필요하다.
BFS(너비 우선 탐색)
Breadth First Search. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다. DFS와는 반대된다고 볼 수 있다.
BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다.
인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 먼저 들어온 것이 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.
알고리즘 진행방식
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
- 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다.
그림으로 보는 간단한 예제
아래의 그래프의 경우라고 생각해보자.
인접한 노드가 여러 개 있을 때는, 숫자가 작은 노드부터 먼저 큐에 삽입한다고 가정하자.
이후 아래의 진행step의 왼쪽의 표는 큐라고 생각한다.
삽입할 땐 위에서 들어오고 꺼낼 땐 아래쪽에서 나간다.
방문 처리된 노드는 회색으로, 큐에서 꺼낸 현재 처리하는 노드는 하늘색으로 표현한다.
[step1] 시작 노드인 '1'을 큐에 삽입하고 방문 처리를 한다.
[step2] 큐에서 노드 '1'을 꺼내고 방문하지 않은 인접 노드 '2', '3', '8'을 모두 큐에 삽입하고 방문 처리를 한다.
[step3] 큐에서 노드 '2'를 꺼내고 방문하지 않은 인접 노드 '7'을 큐에 삽입하고 방문 처리를 한다.
[step4] 큐에서 노드 '3'을 꺼내고 방문하지 않은 인접 노드 '4'와 '5'를 모두 큐에 삽입하고 방문 처리를 한다.
[step5] 큐에서 노드 '8'을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시한다.
[step6] 큐에서 노드 '7'을 꺼내고 방문하지 않은 인접 노드 '6'을 큐에 삽입하고 방문 처리를 한다.
[step7] 남아있는 노드에 방문하지 않은 인접 노드가 없다. 따라서 모든 노드를 차례대로 꺼내면 최종적으로 다음과 같다.
[결과] 노드의 탐색 순서(큐에 들어간 순서)는 아래와 같다.
1 → 2 → 3 → 8 → 7 → 4 → 5 → 6
Python 실제 코드
BFS는 큐 자료구조에 기초하므로 구현이 간단한 편이다.
python의 경우 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·2차원 배열을 그래프 형태로 생각하면 문제를 조금 더 수월하게 풀 수 있다.
예를 들어 게임 맵이 3x3 형태의 2차원 배열이고, 각 데이터가 좌표라고 생각해보자.
게임 캐릭터 시작이 (1,1)좌표에 있다고 생각해봤을 때, 좌표를 상하좌우로만 이동할 수 있다면
아래의 그림처럼 그래프의 형태로 바꿔서 생각할 수 있다.
코테 중에 2차원 배열에서의 탐색 문제를 만나면 이런 식으로 생각해보면 풀이를 좀 더 쉽게 떠올 릴 수 있다.
BFS를 이용하는 간단한 문제(미로탈출)
A씨는 N x M 크기의 직사각형 형태의 미로에 갇혀 있다.
미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다.
A씨의 위치는 (1,1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한번에 한 칸씩 이동할 수 있다.
이 때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다.
미로는 반드시 탈출할 수 있는 형태로 제시된다.
이 때 A씨가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오.
칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.
입력조건
첫째 줄에 두 정수 N,M(4<=N, M<=200)이 주어집니다.
다음 N개의 줄에는 각각 M개의 정수(0또는1)로 미로의 정보가 주어진다.
각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.
출력 조건
첫째 줄에 최소 이동 칸의 개수를 출력한다.
입력 예시
5 6
101010
111111
000001
111111
111111
출력 예시
10
정답코드
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())))
print(graph)
# 이동할 네 방향 정의(상, 하, 좌, 우)
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))
# 가장 오른쪽 아래까지의 최단 거리 반환
print(graph)
return graph[n-1][m-1]
# BFS를 수행한 결과 출력
print(bfs(0,0))느낀점
그래프에 대한 이해도가 부족한 것 같다.
트리/그래프에 대해 공부를 한 번 더 하여 정리를 하고자 한다.
출처
