탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
그 중에서 DFS / BFS를 가장 많이 활용
1. 스택(Stack) : DFS에서 활용
2. 큐(Queue) : BFS에서 활용
from collections import deque
# 큐(Queue) 구현을 위해 덱(Deque) 라이브러리 이용
queue = deque()
# 예 : 삽입(5)-삽입(2)-삽입(3)-삽입(7)-삭제()-삽입(1)-삽입(4)-삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()
print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력
3. 재귀함수 : 자기 자신을 다시 호출하는 함수로 DFS에 많이 사용하는 개념
문제풀이 시에는 종료 조건을 반드시 명시해야 함
컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임
그래서 구현 상 스택 라이브러리 대신 재귀 함수를 이용하는 경우가 많음
깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
스택 혹은 재귀함수 이용
탐색 시작 노드를 스택에 삽입하고 방문처리
스택 최상단 노드 중 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리
없다면, 스택에서 최상단 노드를 꺼냄
2번을 수행할 수 없을 때까지 반복
-예시 그래프- 적은 숫자 노드부터 방문한다고 설정
[Step 1] 시작 노드인 1을 스택에 삽입 후 방문처리
[Step 2] 인접 노드 2,3,8 중 가장 작은 2를 스택에 넣고 방문처리
[Step 3] 최상단 노드의 방문하지 않은 인접 노드 7을 스택에 넣고 방문처리
[Step 4] 방문하지 않은 인접 노드 중 작은 6을 스택에 넣고 방문처리
[Step 5] 6을 스택에서 꺼내줌
[Step 6] 방문하지 않은 인접 노드 8을 스택에 넣고 방문처리
[Step 7] 반복
방문 순서 : 1-2-7-6-8-3-4-5
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(graph, 1, visited)
BFS는 너비 우선 탐색이라고 부르며 가까운 노드부터 우선적으로 탐색하는 알고리즘
큐 자료구조를 이용
탐색 시작 노드를 큐에 삽입하고 방문처리
큐에서 노드를 꺼낸 후 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 하고 방문처리
2번의 과정을 수행할 수 없을 때까지 반복
-예시 그래프- 적은 숫자 노드부터 방문한다고 설정
[Step 1] 시작 노드인 1을 큐에 삽입 후 방문처리
[Step 2] 큐에서 1을 꺼내고 인접 노드 2,3,8을 큐에 넣고 방문처리
[Step 3] 큐에서 2를 꺼내고 방문하지 않은 인접 노드 7을 큐에 넣고 방문처리
[Step 4] 큐에서 3을 꺼내고 방문하지 않은 인접 노드 4, 5를 큐에 넣고 방문처리
[Step 5] 반복
방문 순서 : 1-2-3-8-7-4-5-6
from collections import deque
#BFS 메서드 정의
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
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False]*9
bfs(graph, 1, visited)