그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종
그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말합니다.
깊이 우선 탐색 (Depth-First Search) DFS
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
최대한 멀리 있는 노드 우선 탐색
스택 자료구조 또는 재귀함수 이용
→ 선입후출
너비 우선 탐색 (Breadth-First Search) BFS
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
가까운 노드부터 탐색
모든 간선의 길이(비용)이 동일할 때 이용
주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택
큐 자료구조 이용
→ 선입선출
DFS와 BFS의 시간복잡도
두 방식 모두 조건 내의 모든 노드를 검색
→ 시간 복잡도는 동일
다음 노드가 방문하였는지를 확인하는 시간 + 각 노드를 방문하는 시간
알고리즘 문제 유형
단순히 그래프의 모든 정점을 방문하는 것이 주요한 문제
DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관X
경로의 특징을 저장해둬야 하는 문제
각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용
ex) 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제
최단거리 구해야 하는 문제
미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리
너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에 경로 탐색 시 먼저 찾아지는 해답이 곧 최단거리
검색 대상 그래프가 정말 크다면 DFS
검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS
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]
]
#각 노드가 방문된 정보를 리스트 자료형으로 표현
visited=[False]*9
#정의된 DFS 함수 호출
#노드 탐색 순서 출력
dfs(graph,1,visited)
BFS 큐 자료구조 동작 과정
탐색 시작 노드 큐에 삽입 → 방문 처리
큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드 모두 큐에 삽입
2번 과정 반복
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]
]
#각 노드가 방문된 정보를 리스트 자료형으로 표현
visited=[False]*9
#정의된 BFS 함수 호출
bfs(graph,1,visited)
