알고리즘 - DFS BFS

드라마를 볼 경우

그래프에서 깊은 부분을 우선적으로 탐색하는 방식이다.

1 -> 2 -> 3 -> 4 -> 6 -> 5

1. 경로 탐색 유형(최단거리, 시간)

A점부터 B점까지의 최단 거리와 시간을 구하라.

2. 네트워크 유형(연결)

여러 개체들이 주어진 상태에서 연결되어있는 그룹의 개수를 구하거나, 개체가 같은 네트워크 안에서 연결되어 있는지 확인하는 문제

3. 조합 유형(모든 조합 만들기)

여러가지의 조합을 전부 만들고 비교해봐야 하는 문제

한놈만 끝까지 패는 유형이기 때문에 재귀가 유리하다. 재귀를 타고 타고 타서 탈출조건에 먼저 도달하고 값을 바꿔가는 식으로 구현

트리나 그래프를 순회하거나 찾는 알고리즘이다. 소스 노드에서 시작해 다음 레벨의 근방 노드로 움직이기 전까지 가장 가까이에 있는 노드부터 탐색해 나간다.

너비 우선 탐색은 방향성이 있는 그래프와 방향성이 없는 그래프 모두에 사용될 수 있다.

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

순서가 보장되어야 하기때문에 Queue/LinkedList를 사용

1. 시작점에 연결된 Vertex(노드) push

2. 찾은 Vertex를 Queue에 저장

3. Queue의 가장 첫 번째를 pop

| 1 | -> | 1, 2, 5 | -> | 2, 5 | -> | 2, 5, 3 | -> | 5, 3 | -> | 5, 3, 4 | -> | 3, 4 | -> | 4 | -> | 4, 6 | -> | 6 | -> | |

너비 우선 순회