그래프 탐색 방법
> 넓이 우선 탐색 == BFS (Breath First Search)
-> A B C D G H I E F J
> 깊이 우선 탐색 == DFS (Depth First Search)
-> A B D E F C G H I J
1. BFS
- 너비를 우선적으로 탐색 ( 모든 정점과 간선을 방문하는 완전탐색 )
- 정점의 인접한 노드를 먼저 탐색하는 방식
- BFS는 가중치 없는 그래프 (간선의 가중치가 모두 1인 그래프) 에서 최단 경로를 찾아줌
- Queue 를 활용
코드
def bfs(graph, start_node):
visit = list()
queue = list()
queue.append(start_node)
while queue :
node = queue.pop(0)
if node not in visit :
visit.append(node)
queue.extend(graph[node])
return visit
2. DFS
- 깊이를 우선적으로 탐색 ( 모든 정점과 간선을 방문하는 완전탐색 )
- 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동
- 정점의 자식들을 먼저 탐색하는 방식
- 재귀함수 Recursion 또는 Stack 사용
코드
def dfs(graph, start_node):
visit = list()
stack = list()
stack.append(start_node)
while stack :
node = stack.pop()
if node not in visit :
visit.append(node)
stack.extend(graph[node])
return visit* 관련 필요 알고리즘 지식
- 위상정렬
- 최소신장트리
- 최단거리
* BFS, DFS 관련 코딩테스트 유형 예시
- 그래프의 모든 정점을 방문할 때
- 트리 순회
- 부분 상태 탐색 (위치 이동, 수 이동 등 )
- 전체 상태 탐색 (전체 맵을 탐색하는 경우 -> 방향벡터 사용 )
- Flood Fill 색채우기
DFS
- 모든 관계 탐색
- 경로의 특징을 저장해둬야 하는 문제 ( BFS 는 경로의 특징을 가지지 못함)
- 검색 대상 그래프가 정말 클 때
BFS
- 가까운 관계 탐색
- 최단거리 구해야 하는 문제
깊이 우선 탐색(DFS)으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있음.
너비 우선 탐색(BFS)으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리 - 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않을 때
* 사용 시 유의사항
- BFS, DFS 를 언제 사용해야 하는 지 알기
(BFS 로만, DFS로만 해결가능한 문제가 있기에 무조건적인 접근 X ) - 재귀함수 사용 시 오류방지 limit 코드 작성하기
import sys
sys.serrecursionlimit* BFS, DFS 관련 백준문제
BFS
- 미로탐색 https://www.acmicpc.net/problem/2178
-> 풀이 : https://velog.io/@mong7399/python-2178번-미로탐색 - 연구소 https://www.acmicpc.net/problem/14502
-> 풀이 - 아기상어 https://www.acmicpc.net/problem/16236
-> 풀이 : https://velog.io/@mong7399/python-16236-아기상어 - 다리만들기 https://www.acmicpc.net/problem/2146
-> 풀이 :
DFS
참고
https://devuna.tistory.com/32
https://itholic.github.io/python-bfs-dfs/
