선형 탐색 = i번째 상태를 탐색한 후 다음 i+1번째 탐색 상태가 한가지일 때
선형 탐색법 = 순차 탐색, 이분 탐색
비선형 탐색 = i번째 상태 탐색 후 다음 i+1번째 상태가 2개 이상일 때 ex) 트리, 그래프
비선형 탐색법 = DFS, BFS
1. 그래프의 구현
그래프의 구현은 크게 인접 행렬과 인접 리스트로 나눌 수 있다.
입력으로 정점(n), 간선(m)이 주어지고
m개의 줄에 걸쳐 간선으로 연결된 두 정점의 번호와 가중치가 입력으로 주어질 때
1) 인접 행렬의 구현
2차원 배열을 이용해 표현한다.
최대 정점 수에 맞춰 2차원 배열을 선언하고 각 배열의 칸에 연결된 정보를 저장한다.
모든 정점을 탐색하는 데 O(nm)
인접행렬 소스코드
n, m = map(int, input().split())
arr = [[0]*m for _ in range(n)]
for i in range(0, m):
a, b, w = map(int, input().split())
arr[a][b] = arr[b][a] = w
2) 인접 리스트의 구현
인접 행렬에서는 그래프가 연결되지 않는 부분에 0을 넣음으로써 모두 표현한다.
일반적인 그래프는 행렬상에서 0으로 표현해야 하는 부분이 많을 가능성이 큰데 알고리즘을 구현할 때 이 0을 모두 탐색하는 것은 효율이 떨어진다.
이러한 단점을 극복하기 위해 인접 리스트가 제안되었다.
인접 리스트에선 0으로 표시된 부분은 저장하지 않는다.
위 입력 데이터를 바탕으로 인접 리스트를 구현한다면 위 그림과 같은 연결 리스트 형태로 구현할 수도 있지만, STL에서 제공하는 std::vector을 이용하면 더 간단하다.
std::vector을 이용하면 인접 행렬로 구현하는 것보다 공간을 적게 사용한다. 따라서 전체 탐새겁을 구현할 때 역시 탐색 시간을 줄일 수 있다. 모든 정점을 탐색하는 데 O(n+m)
그래프 = 사이클 O
트리 = 사이클 X
*사이클 = 임의의 한 정점에서 출발하여 1개 이상의 간선을 거쳐 다시 출발했던 정점으로 되돌아오는 경로
2. 깊이 우선 탐색(DFS)
DFS = 기준점으로부터 모든 정점들을 깊이 우선으로 탐색한다.
왼쪽 정점부터 방문한다 가정하면, 순서는 다음과 같다.
깊이 우선 탐색은 (e)단계 이후 더 이상 진행할 수 있는 정점이 없다.
이처럼 더 이상 진행할 수 없을 때 다시 이전 정점으로 되돌아가는 백트랙(backtrack)의 과정이 필요하다.
백트랙은 비선형 구조의 탐색에서 아주 중요하며 스택이나 재귀 함수를 통해 구현할 수 있다.
정리하자면 깊이 우선 탐색이란
1) 시작 정점에서 간선을 하나 선택
2) 깊이 우선으로 최대한 진행
3) 더이상 진행할 수 없을 때 백트랙하여 다시 2)로 되돌아감
모든 정점을 방문할 때까지 위 과정을 반복한다.
O(n^2)
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 = [
[],
[],
...
]
visited = [False]*10
print("방문순서")
dfs(graph, 1, visited)
3. 너비 우선 탐색(BFS)
BFS = 현재 정점에서 깊이가 1인 정점을 모두 탐색한 뒤 깊이를 늘려가는 방식
너비 우선 탐색은 백트랙을 하지 않는다. 대신 현재 정점으로부터 깊이가 1인 정점을 모두 방문해야 하므로 큐의 선입선출 자료 구조를 활용한다.
BFS 소스코드(인접 행렬) = O(n*2)
from collections import deque
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 = [
[],
[],
...
]
visited = [False] * 9
bfs(graph, 1, visited)