[Algorithm] DFS, BFS

1. DFS, Depth First Search. 깊이우선탐색
   
   정점의번호가 모두 유일할때, 현재 탐색중인 정점과 인접한 정점들을 정점번호가 낮은순으로 가장 깊이 탐색하는 방법이다.
   그림에서보면알다싶이 같은 레벨(2-3-4, 5-6-7-8, 9-10-11)을 무시한채, 현재 탐색중인 정점에 인접한 정점들을 우선방문하는 속성이 메커니즘이된다. 따라서 LIFO구조를 지닌 스택(또는 재귀함수)을 이용하여 구현가능하다.

   • 찾고자하는 정보가 깊은레벨일 수록 BFS보다 효율적
   • 최단경로보장 X
   • 깊이가 무한한경우, 깊이제한을 두며 구현할때가 있다.(다시 부모로돌아간다 => 백트래킹)
   • 적은 메모리공간 사용

2. BFS, Breath First Search. 너비우선탐색
   
   그림처럼 같은 레벨의 정점들을 우선 탐색하는 방법이다. 이미 넣은 정점들정보들을 우선 탐색하면되므로, FIFO구조인 큐를 이용하여 구현가능하다.

   • 구해진 해가 최단경로이다.
   • 경로에 비례하여 필요한 메모리공간이 증가한다.
   • 무한그래프인경우 종료시점을 못찾는다.

DFS, BFS 관련문제들 풀이 >
https://velog.io/@cldhfleks2/1260
https://velog.io/@cldhfleks2/16173

아래는 구현할때 필요한 포인트이다.

1. DFS : 스택,재귀함수로 구현
2. BFS : 큐로 구현
3. 정점이 무엇인지 정점들간의 관계를 어떻게 구현할지 (+가중치가있는가..)
4. 방문한정점들을 체크(재방문 없이)