+ 이 글은 작성자가 직접 공부하고 복습하며 작성한 글입니다. 만약 직접 작성하지 않았다면, 꼭 출처를 밝히겠습니다!
+ 이 글은 개인적인 공부를 바탕으로 작성되었기에, 틀린 부분이 있을 수 있으며, 틀린 부분이 있다면 알려주시면 감사하겠습니다!
+ 이 글을 다른 곳으로 가져가신다면, 꼭 출처를 남겨주세요~
+ '참고사이트'는 공부하기 위해 참고한 사이트들을 모아 둔 것입니다.
+ 혹시라도 문제가 된다면 바로 조취를 취할테니, 말해주시면 감사하겠습니다!
그래프 탐색에는 여러 알고리즘이 있지만, 가장 대표적으로 DFS와 BFS가 있습니다.
<간단 비교>
+ DFS(Depth First Serch)
- '깊이 우선 탐색';
- 현재 정점에서 갈 수 있는 점들 중, 한 곳을 우선적으로 끝까지 탐색;
- 스택이나 재귀함수로 구현;
+ BFS(Breadth First Serch)
- '너비 우선 탐색';
- 현재 정점에서 갈 수 있는 점들부터 탐색;
- 큐를 이용해서 구현;
[ DFS ]
+ DFS는 Depth First Search로 '깊이 우선 탐색'이라는 뜻의 알고리즘입니다. 말 그대로 한 점에서 갈 수 있는 곳을 최우선으로 파고들어간 다음, 다음 정점으로 가 그 정점에서의 끝까지 탐색합니다.
+ DFS 구현을 위해서 대부분 '스택'과 '재귀함수'를 이용합니다. 왜냐하면 처리 구조가 DFS와 같기 때문입니다. 밑의 그림을 참고해주세요.
+ 표에서 나오는 바와 같이,
1) A에서 갈 수 있는 곳 X가 스택에 들어가고,
2) 그 다음 X에서 갈 수 있는 H,G가 스택에 들어갑니다.
3) 그 다음, LIFO(Last In, First Out)이므로 H에서 갈 수 있는 EPG가 스택에 들어갑니다. 여기서 G는 이미 스택에 쌓여있기에 스택에 추가되지 않습니다.
+ 이런 식으로, 스택의 가장 위에있는 정점에서 갈 수 있는 정점들을 스택에 집어넣고 그곳을 탐색하는 것을 반복해서 모두 탐색하는 것이 DFS입니다.
+ 만약 정점 간에 부모, 자식 관계가 있다면, 같은 부모는 스택에 넣고 자식부터 탐색하는 것이 DFS입니다.
*** 참고해야할 점
- 방문했던 정점을 재 탐색 하지 않기위해, 따로 배열을 만들어서 방문한 곳인이 체크해야합니다.
- 완전 탐색 입니다.
- 트리에서 최단 거리 탐색 가능합니다.
- 가중치 및 비가중치 그래프에서는 거의 사용되지 않습니다.(불가능하다, 가능은하나... 와 같은 여러 의견들이 있습니다)
[ BFS ]
+ BFS는 Breadth First Search로 '너비 우선 탐색'을 뜻하는 알고리즘입니다. 위에서 말씀드린 DFS와는 달리, 현재 정점에서 갈 수 있는 곳들을 다 탐색하고, 탐색한 곳에서 갈 수 있는 정점들을 탐색합니다.
+ BFS 구현을 위해서 대부분 '큐'를 이용해 구현합니다. 왜냐하면 처리 구조가 BFS와 같기 때문입니다.
+ 표에서 보이는 바와 같이
1) A에서 갈 수 있는 곳 X가 큐에 들어가고,
2) X에서 갈 수 있는 H,G가 큐에 들어갑니다.
3) 그 뒤, H,G를 탐색하면서 해당 정점에서 갈 수 있는 정점들을 큐에 넣습니다.
+ 이런 식으로 정점에서 갈 수 있는 정점들을 먼저 탐색한 뒤, 탐색한 정점들에서 갈 수 있는 정점을 탐색하는 것을 반복해서 모두 탐색하는 것이 BFS 알고리즘 입니다.
*** 참고해야할 점
- 방문했던 곳을 재 방문 하지않기위해, 따로 배열을 만들어서 체크해야합니다.
- 완전 탐색입니다.
- 트리에서 최단거리 탐색이 가능합니다.
- 비가중치 그래프에서 최단거리 탐색이 가능합니다. (다익스트라보다 효율이 좋다고 합니다.)
- 가중치 그래프에서는 잘 사용되지 않습니다.
[ Code ]
+ https://www.acmicpc.net/problem/1260 문제의 풀이 과정으로 사용했습니다.
** 참고사이트 **
- https://twpower.github.io/73(How-to-implement-dfs-and-bfs-in-c++)
- https://www.zerocho.com/category/Algorithm/post/5870153c37e1c80018b64eb0
Copyright © -강정이좋아- 무단 전재 및 재배포는 하지 말아주세요.
'요리 레시피 > Algorithm' 카테고리의 다른 글
| [BaekJoon] 이항계수, 페르마의 소정리, 거듭제곱 feat.11401번(이항계수3) (0) | 2018.05.12 |
|---|---|
| [다익스트라] 다익스트라 - 유명한 최단거리 찾기 알고리즘!!! (0) | 2018.03.27 |
| [Dp] DP에서 배열 사용 (0) | 2018.03.26 |
| [BackJoon] 충격의 N-Queen 문제 feat.9663번(N-Queen) (0) | 2018.03.26 |
| [BaekJoon] 생각의 전환 feat.2225번(합분해) (0) | 2018.03.26 |