탐색 알고리즘 DFS / BFS
*이코테 with 파이썬 정리노트입니다.
📍꼭 필요한 자료구조 기초
스택(Stack) 선입후출 구조 또는 후입선출 구조
stack = []
# 삽입(5-2-3-7) - 삭제 - 삽입(4) - 삭제
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop() #7 삭제
stack.append(1)
stack.append(4)
stack.pop() #4 삭제
print(stack) #[5,2,3,1]append()와 pop()메서드를 이용하면 스택 자료구조와 동일하게 동작한다.
append()는 가장 뒤쪽에 데이터를 삽입, pop()메서드는 리스트의 가장 뒤쪽에서 데이터를 꺼낸다.
큐(Queue) 선입선출 구조
from collections import deque
queue = deque()
# 삽입(5-2-3-7) - 삭제 - 삽입(1-4) - 삭제
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft() #5 삭제
queue.append(1)
queue.append(4)
queue.popleft() #2 삭제
print(queue) #deque([3,7,1,4])📌 파이썬으로 큐를 구현할때는 collections모듈에서 제공하는 라이브러리를 사용하는게 효율적이다!
DFS
DFS는 깊이우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
DFS는 스택 자료구조(혹은 재귀함수)를 이용한다.
📍DFS 알고리즘
- 탐색 시작 노드를 스택에 삽입하고 방문 처리.
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문.
방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄. - 더 이상 2번의 과정을 수행할 수 없을 때까지 반복.
def dfs(graph,v,visited):
#현재 노드를 방문 처리
visited[v] = True
#현재 노드와 연결된 다른 노드를 재귀적으로 방문
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)📌 DFS 스택을 이용하는 알고리즘이기 때문에 실제 구현은 재귀 함수를 이용했을 때 매우 간결하게 구현 가능!
BFS
BFS는 너비우선 탐색이라고도 부르며, 가까운 노드부터 탐색하는 알고리즘
BFS는 큐 자료구조를 이용한다.
📍BFS 알고리즘
- 탐색 시작 노드를 큐에 삽입하고 방문 처리.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복.
from collections import deque
def bfs(graph, start, visited):
queue = deque([start]) #시작 노드를 큐에 넣고 시작
#현재 노드를 방문처리
visited[start] = True
#큐가 빌 때까지 반복
while queue:
#큐에서 하나의 원소를 뽑아 출력하기
v = queue.popleft()
#아직 방문하지 않은 인접한 원소들을 큐에 삽입
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
#정의된 DFS함수 호출
bfs(graph,1,visited)| DFS | BFS | |
|---|---|---|
| 동작 원리 | 스택 | 큐 |
| 구현 방법 | 재귀 함수 이용 | 큐 자료구조 이용 |
iOS / Swift