이코테 강의 정리 - DFS/BFS
그래프 탐색 알고리즘 : DFS / BFS
- 타색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
- 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있음 → 자주 출제됨
스택
- 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조
- 입구와 출구가 동일한 형태로 스택을 시각화할 수 있음
stack = []
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(2)
stack.append(2)
stack.pop()
print(stack[::-1]) # 최상단 원소부터 출력
print(stack) # 최하단 원소부터 출력
큐
- 먼저 들어온 데이터가 먼저 나가는 형식(선입선출) 자료구조
- 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 가능
from collections import deque
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
queue.append(5) #가장 오른쪽에 숫자 추가
queue.popleft() # 가장 왼쪽에 숫자 제거
print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력
재귀함수(Recursive Function)
-
재귀함수란 자기 자신을 다시 호출하는 함수를 의미한다.
-
재귀함수 사용시 유의사항
- 재귀함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성 가능 단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수 있으므로 신중하게 사용
- 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있음
- 재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있음
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다. → 그래서 스택을 사용해야 할 떄 구현상 스택 라이브러리 대신 재귀 함수를 이용하는 경우가 많음
DFS(Depth-First Search)
- DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
- DFS는 스택 자료구조(혹은 재귀함수)를 이용하며 구체적인 동작 과정은 다음과 같음
- 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 더 이상 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)
# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9
#정의된 DFS 함수 호출
dfs(graph, 1, visited)
BFS(Breadth-First Search)
- BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
- BFS는 큐 자료구조를 이용하며 구체 적인 동작 과정은 다음과 같다
- 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
stack = []
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(2)
stack.append(2)
stack.pop()
print(stack[::-1]) # 최상단 원소부터 출력
print(stack) # 최하단 원소부터 출력
from collections import deque
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
queue.append(5) #가장 오른쪽에 숫자 추가
queue.popleft() # 가장 왼쪽에 숫자 제거
print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력
재귀함수란 자기 자신을 다시 호출하는 함수를 의미한다.
재귀함수 사용시 유의사항
- 재귀함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성 가능 단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수 있으므로 신중하게 사용
- 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있음
- 재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있음
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다. → 그래서 스택을 사용해야 할 떄 구현상 스택 라이브러리 대신 재귀 함수를 이용하는 경우가 많음
- 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 더 이상 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)
# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9
#정의된 DFS 함수 호출
dfs(graph, 1, visited)
- 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
→ 최단거리 문제에서 활용될 수 있다!
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
# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9
#정의된 DFS 함수 호출
bfs(graph, 1, visited)
✨ deque, heapq 차이 및 사용법
-
deque
-
선입선출, BFS
from collections import deque q = deque() q.append(1) # 오른쪽에 원소 추가 q.popleft() # 왼쪽에 원소 제거
-
-
heapq
- 최소힙, 최대힙
- 다익스트라, 최소값이나 최대값을 빨리 찾아야 할 때
import heapq heap = [] heapq.heappush(heap, 1) # 원소 추가 heapq.heapop(heap) # 원소 제거 # 기존 리스트를 heap으로 변환 heap2 = [1, 2, 3] heapq.heapify(heap2) # 최대힙 a = [1, 2, 5, 3] heap3 = [] for i in a: heapq.pheapush(heap3, -i) for i in range(4): print(-heapq.heapop(heap3))
Author And Source
이 문제에 관하여(이코테 강의 정리 - DFS/BFS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ssulv3030/이코테-강의-정리-DFSBFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)