사전 지식
탐색
많은 양의 데이터 중 원하는 데이터를 찾는 과정
자료구조
데이터를 표현하고, 관리하고, 처리하기 위한 구조
스택과 큐에 대해 잘 모른다면 아래 글을 참고할 것
2021/02/01 - [개발 일지/Algorithm] - 파이썬에서의 스택(Stack)과 큐(Queue)
재귀함수
자기 자신을 호출하는 함수. 수학의 점화식을 코드화한 것
- 점화식: 특정 함수를 자기보다 더 작은 변수와 함수의 관계로 표현한 것
- 재귀 함수는 점점 작아지는 자기 자신 + 종료 조건을 통해 동작한다.
그래프
그래프에 대해 잘 모른다면 아래 글을 참고할 것
2021/02/01 - [개발 일지/Algorithm] - [Data Structure] 그래프(Graph)
DFS (깊이 우선 탐색, Depth-First Search)
개념
더 이상 방문하지 않은 노드가 없을 때까지 인접 노드를 선택하여 탐색하는 방식
인접 노드간에는 정해진 우선 순위가 있지는 않으나 보통 크기가 작은 순서대로 탐색
구현(Python)
스택과 재귀함수를 이용하여 구현하는 것이 일반적이다.
방문한 노드, 인접한 노드를 스택에 추가하고 인접 노드 중 미방문인 노드가 없을 시 꺼낸다.
나는 가중치가 있는 경우 인접 행렬을, 없는 경우 인접 리스트를 이용한다.
인접 행렬
INF = 987654321
def dfs(graph, v, visited):
visited[v] = True
print(v, end=" ")
for i in range(len(graph[0])):
if graph[v][i] != 0 and graph[v][i] != INF and not visited[i]:
dfs(graph, i, visited)
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]
visited = [False] * len(graph[0])
start = 1
dfs(graph, start, visited)
인접 리스트
def dfs(graph, v, visited):
visited[v] = True
print(v, end=" ")
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
vertex = 4
graph = [
[2, 3],
[2],
[0, 1],
[0]
]
start = 1
visited = [False] * vertex
dfs(graph, start, visited)시간 복잡도
dfs 함수(곧 반복문)는 정점의 개수만큼 호출되고, 반복문은 graph[v] == 간선의 개수만큼 순회하므로 인접 행렬의 경우 O(V + E), 인접 그래프의 경우 O(V^2)이다.
BFS(너비 우선 탐색, Breadth-First Search)
개념
인접 노드를 모두 방문한 뒤 그 중 가장 먼저 방문한 인접 노드의 인접 노드를 방문하는 방식
구현(Python)
큐를 이용하여 구현하는 것이 일반적이다.
큐에서 꺼낸 노드의 인접 노드를 순회하며 미방문된 노드를 큐에 넣는다.
마찬가지로 가중치가 있는 경우 인접 행렬을, 없는 경우 인접 리스트를 이용한다.
인접 행렬
from collections import deque
INF = 987654321
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
print(v, end=" ")
for i in range(len(graph[0])):
if graph[v][i] != 0 and graph[v][i] != INF and not visited[i]:
queue.append(i)
visited[i] = True
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]
start = 1
visited = [False] * len(graph[0])
bfs(graph, start, visited)
인접 리스트
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
vertex = 4
graph = [
[2, 3],
[2],
[0, 1],
[0]
]
start = 1
visited = [False] * vertex
bfs(graph, start, visited)