탐색(Search)이란?
- 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
- 대표적인 그래프 탐색 알고리즘으로는 DFS(Depth-First Search)와 BFS(Breadth-First Search)가 있음
- DFS/BFS는 코딩테스트 빈출유형이므로 반드시 숙지해야 함
DFS(Depth-First Search)란?
- 깊이우선탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- 스택 자료구조(혹은 재귀함수)를 사용
- 동작 과정
- 탐색 시작 노드를 스택에 push, 방문 처리
- 스택 최상단에 방문하지 않은 인접한 노드가 있으면 push, 방문 처리(단, 방문하지 않은 노드가 없으면 pop)
- 더 이상 2. 의 과정을 수행할 수 없을 때까지 반복
def dfs(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
visited_s = [False] * 9
graph_s = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
dfs(graph_s, 1, visited_s)
BFS(Breadth-First Search)란?
- 너비우선탐색이라고도 부르며 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
- 큐 자료구조 이용
- 동작 과정
- 탐색 시작 노드를 큐에 push, 방문 처리
- 큐에서 노드를 pop, 해당 노드의 인접노드 중 방문하지 않은 노드를 모두 큐에 push하고 방문처리
- 더 이상 2. 의 과정을 수행할 수 없을 때까지 반복
from collections import deque
def bfs(graph, start, visited):
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
visited_s = [False] * 9
graph_s = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
bfs(graph_s, 1, visited_s)
'자료구조 & 알고리즘(Data Structure & Algorithm) > 알고리즘(Python)' 카테고리의 다른 글
동적계획법(Dynamic Programming) (0) | 2022.02.23 |
---|---|
순차 탐색 &이진 탐색 (0) | 2022.02.22 |
스택(Stack), 큐(Queue), 재귀(Recursion) (0) | 2022.02.14 |
구현(Implementation) (0) | 2021.08.03 |
그리디 알고리즘(Greedy Algorithm) (1) | 2021.07.29 |