욤미의 개발일지
CHAPTER 5. DFS, BFS 본문
탐색(Search)란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.
DFS와 BFS는 대표적인 그래프 탐색 알고리즘이다.
자주 등장하는 유형이기때문에 꼭 숙지해야한다!
1. DFS(Depth First Search) 깊이 우선 탐색
- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- 스택 혹은 재귀함수를 이용한다.
동작 과정
- 탐색을 시작하는 노드를 스택에 삽입하고 방문 처리 한다.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리한다.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 더 이상 2, 3번의 과정을 수행할 수 없을 때까지 반복한다.
def dfs(graph, v, visited):
visited[v] = True # 현재 노드 방문 처리
print(v, end = ' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]: # 방문하지 않은 상태라면 dfs 실행
dfs(graph, i, visited)
# 각 노드가 연결된 정보를 표현(2차원 리스트)
# 0번 노드는 비워둠
graph =[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 각 노드가 방문된 정보를 표현(1차원 리스트)
# 기본적으로 방문하지 않은 False로 초기화 0번 노드는 사용하지 않기때문에 하나더 큰 크기로 초기화
visited = [False] * 9
# 정의된 DFS 함수 호출
dfs(graph, 1, visited) # 그래프 정보, 시작노드, 방문 정보
'''
실행결과: 1 2 7 6 8 3 4 5
'''
2. BFS(Breadth First Search) 너비 우선 탐색
- 정점과 같은 레벨에 있는 노드들(형제 노드)을 먼저 탐색하는 방식
- 가까운 노드부터 우선적으로 탐색하며 큐 자료구조를 이용한다.
- 큐 자료구조 이용에 대한 숙지가 필요하다.
동작 과정
- 탐색을 시작하는 노드를 큐에 삽입하고 방문 처리한다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
- 더 이상 2번의 과정을 수행할 수 없을 때 까지 반복한다.
from collections import deque
def bfs(graph, v, visited):
queue = deque([start]) # 큐 구현을 위해 deque 라이브러리 사용
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
# 정의된 BFS 함수 호출
bfs(graph, 1, visited)
'''
실행결과: 1 2 3 8 7 4 5 6
'''
728x90
'Algorithm > 이것이 코딩테스트다' 카테고리의 다른 글
CHAPTER 6. 정렬 - 삽입 정렬 (0) | 2021.06.24 |
---|---|
CHAPTER 6. 정렬 - 선택 정렬 (0) | 2021.06.23 |
CHAPTER 6. 정렬 (0) | 2021.06.22 |
CHAPTER 4. Implementation (0) | 2021.05.15 |
CHAPTER 3. Greedy (0) | 2021.05.14 |
Comments