티스토리 뷰
알고리즘이 나를 미치게한다 ㅋ
공부합시다 열어분,,
오늘은 DFS와 BFS에 대해 알아보겠습니다!
| DFS(Depth First Search)란?
- 그래프에서 다른 노드를 방문하기 전에 하나의 노드를 깊게 파고들며 순회하는 검색 알고리즘입니다.
(깊이 우선 탐색 알고리즘이라고 불리죠.)
- Stack또는 재귀함수를 이용해서 구현합니다.
- 추가적으로 DFS를 이용할 때 "재귀호출(Recursion)"을 이용하면 코드가 훨씬 간결하고 쉬워집니다.
단 stack과 다른점은 자식이 1개 이상인경우
stack : 쌓고 나서 호출하기 때문에 자시중에 맨 마지막으로 들어간 녀석이 먼저 출력이 됩니다.
재귀호출 : 정방향으로 호출하기 때문.
- 그래서 소위 깊이를 우선적으로 탐색한다는 의미로 DFS를 깊이우선검색 이라고 말합니다.
구현방법
1. 탐색 시작 노드를 Stack에 삽입하고 방문 처리를 합니다.
2.Stack의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 Stack에 넣고 방문 처리합니다.
3.방문하지 않은 인접 노드가 없으면 Stack에서 최상단 노드를 꺼냅니다.
4.더 이상 2번과 3번의 과정을 수행할 수 없을 때 까지 반복합니다.
javascript에서 DFS는 Stack이나 재귀함수를 활용하여 풀 수 있습니다.
최상위 Root에서 연결된 자식 노드를 모두 탬색 후 더이상 자식 노드가 없을 때 인접한 상위 노드의 형제 노드를 방문합니다.
해당 형제 노드에서도 자식 노드를 탐색하고, 더 이상 자식 노드가 없을 경우 다시 인접한 상위 형제의 노드를 방문하는 알고리즘입니다.
위의 그림에서 Root(A) Node 부터 B를 따라 자식 노드를 탐색한 뒤, I 노드를 가장 마지막에 탐색합니다.
자바스크립트에서는 재귀 함수를 이용하여 DFS를 구현할 수 있습니다.
각각 노드의 자식 노드를 탐색하는 함수를 Stack(스택)에 추가한 뒤, 더 이상 자식 노드가 없을 때 마지막에 추가된 자식 노드를 먼저 실행 후 스택에서 제거하는 후입선출(LIFO) 방식을 사용합니다.
" DFS는 뭐다 ? LIFO 방식을 사용한다 "
프로그래머스에서 각 노드들은(숫자) 다음 index의 숫자가 더하기(+)인 경우와 빼기(-)인 경우 두 가지의 자식 노드를 갖고 있습니다.
DFS 방법에 따라 모든 숫자가 (+)인 경우를 모두 탐색한 뒤 다음 인덱스의 숫자가 (-)인 경우를 탐색합니다.
| BFS란?
- Que(큐)를 이용한 방법입니다.
- 큐는 위로 집어넣고 아래에서 꺼냅니다. 즉, First In Fist out(FIFO)인 선입선출 방식입니다.
- 너비 우선 탐색이라고 부릅니다.
- 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다.
- 특정 조건의 최단거리 문제로도 해결될 수 있습니다.
동작 과정
1. 탐색 시작 노드를 Que에 삽입하고 방문 처리를 합니다.
2. Que에서 노드를 꺼낸 후 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문처리합니다.
(DFS와 다른점은 인접하지 않은 노드에 대해서 다시 한 번씩 큐에 넣으면서 반복 수행한다는 점과 차이가 있습니다.)
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.
참고 유튜브