BFS(Breadth First Search, 너비 우선 탐색)
일단 오늘 다뤄볼 내용인 BFS와 DFS는 모두 그래프를 탐색할 때 사용하는 기법입니다. 이름에서도 알 수 있듯이 어떤 것을 우선 순위로 하는지 차이라서 코드도 거의 비슷하게 느껴지실 겁니다.
일단 너비 우선 탐색이라고 불리는 BFS는 말 그대로 너비를 우선해서 그래프를 탐색하는 기법인데요, 시작점인 루트 노드와 같은 거리에 있는 노드를 우선으로 방문한다고 보시면 됩니다.
아래 그림을 보시면 확실하게 이해하실 수 있을 것 같네요.
이 알고리즘의 핵심은 큐(queue) 자료구조를 사용하는 것인데요, 노드를 방문하면서 인접한 노드 중 방문하지 않았던 노드의 정보만 큐에 넣어 먼저 큐에 들어있던 노드부터 방문하면 되는 것이죠. 물론 큐를 사용하지 않아도 구현이 가능합니다!
한편, 파이썬에서 큐를 list 타입을 사용해 자료를 입력할 때는 list.append(something), 출력할 때는 list.pop(0) 와 같이 구현하시는 분들이 있습니다.
하지만 list.pop(0) 은 시간복잡도가 O(N) 이라 이렇게 구현하면 시간적으로 매우 비효율적인 코드가 만들어지게 됩니다. [링크]
따라서 collections 라이브러리의 deque 를 사용하면 시간을 절약할 수 있게 됩니다.
또한 인접 노드 중 방문하지 않았던 노드를 큐에 넣을 때는 파이썬 데이터 타입 중 set 을 사용하면 아주 쉽게 구현할 수 있습니다.
파이썬에서 BFS를 구현한 소스 코드 입니다.
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
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)DFS(Depth First Search, 깊이 우선 탐색)
DFS는 BFS와는 다르게 한 놈만 팬다(?)라는 느낌으로 한 방향으로 갈 수 있을 만큼 깊게 탐색한다는 의미에서 깊이 우선 탐색이라는 이름이 붙었습니다.
갈 수 있는 한 끝까지 탐색해 리프 노드를 방문하고, 이전 갈림길에서 선택하지 않았던 노드를 방문하는 식으로 탐색합니다.
이번에도 설명 대신에 이미지로 보시는게 더 확실하게 이해되실 것 같네요.
한편, 여기에서는 BFS에 있던 큐 대신에 스택(stack) 으로 자료구조를 대체하기만 하면 쉽게 구현하실 수 있습니다.
먼저 방문한 노드에 연결된 노드보다 현재 방문한 노드에 연결된 노드를 방문해야 한 방향으로 갈 수 있거든요.
이전과 같은 유향 그래프를 탐색하신다면 이렇게 구현하시면 됩니다.
파이썬에서 DFS를 구현한 소스 코드 입니다.
# DFS 메서드 정의
def dfs(graph, v, visited):
# 현재 노드를 방문 처리
visited[v] = True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)오늘은 DFS, BFS를 이용한 비교적 쉬운 문제를 풀어보았는데, 남은 기간 DFS, BFS에 대해 더 깊게 공부를 해야 할 거 같습니다.
링크텍스트
문제 링크
DFS와 BFS
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 128 MB 230017 86966 51603 36.628%
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
예제 입력 1
4 5 1
1 2
1 3
1 4
2 4
3 4
예제 출력 1
1 2 4 3
1 2 3 4
예제 입력 2
5 5 3
5 4
5 2
1 2
3 4
3 1
예제 출력 2
3 1 2 5 4
3 1 4 2 5
예제 입력 3
1000 1 1000
999 1000
예제 출력 3
1000 999
1000 999
출처
문제를 만든 사람: author5
데이터를 추가한 사람: dfghcvb11, djm03178, doju
어색한 표현을 찾은 사람: doju
빠진 조건을 찾은 사람: pumpyboom
알고리즘 분류
그래프 이론
그래프 탐색
너비 우선 탐색
깊이 우선 탐색
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
def dfs(graph, v, visited):
# 현재 노드를 방문 처리
visited[v] = True
# 현재 노드 번호 출력
print(v, end=' ')
# 현재 노드와 연결된 다른 노드들에 대해서 재귀적으로 DFS 호출
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
def bfs(graph, v, visited):
# BFS를 위한 큐 생성
queue = deque([v])
# 현재 노드를 방문 처리
visited[v] = True
# 큐가 빌 때까지 반복
while queue:
# 큐에서 하나의 원소를 뽑아서 출력
v = queue.popleft()
print(v, end=' ')
# 아직 방문하지 않은 인접한 노드들에 대해서 방문 처리 후 큐에 추가
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
# 노드의 개수, 간선의 개수, 시작 노드 번호 입력
n, m, v = map(int, input().split())
# 노드들의 방문 여부를 저장하는 리스트 초기화
visited1 = [False] * (n + 1) # DFS를 위한 방문 여부 리스트
visited2 = [False] * (n + 1) # BFS를 위한 방문 여부 리스트
# 그래프 초기화
graph = [[] for _ in range(n+1)] # 각 노드에 대한 인접 리스트
for i in range(m):
a, b = map(int, input().split())
graph[a].append(b) # a와 b 사이에 간선 추가
graph[b].append(a) # 양방향 그래프이므로 b와 a 사이에도 간선 추가
# 노드 번호가 작은 순서대로 각 노드에 연결된 간선을 정렬
for i in range(1, n+1):
graph[i].sort()
# DFS, BFS 호출
dfs(graph, v, visited1)
print()
bfs(graph, v, visited2)
print()