[알고리즘]DFS(깊이우선탐색)/BFS(너비우선탐색) 문제유형, 구현방법

그래프 탐색 알고리즘

DFS : 깊이 우선 탐색
BFS : 너비 우선 탐색

1. 대표적인 문제 유형

1) 경로탐색 유형 (최단거리, 시간)
2) 네트워크 유형 (연결) : 여러 개체들이 주어진 상태에서 연결되어 있는 그룹의 개수를 구하거나 두 개체가 같은 네트워크 안에서 연결되어 있는지를 확인
3) 조합 유형 (모든 조합 만들기)

2. 구현 방법

1) DFS > 재귀함수로 풀이

• 모든 경우의 수를 확인한다.

2) BFS > QUEUE / LinkdeList

• 가장 먼저 넣었던 것을 꺼내서 연결된 점을 Queue에 넣기, Queue가 빌 때까지 반복