깊이 우선 탐색(DFS, Depth First Search)
깊이 우선 탐색?
목표한 노드를 찾기 위해 가장 우선 순위가 높은 노드의 자식으로 깊이 들어갔다가 목표 노드가 존재하지 않으면 처음 방문한 노드와 연결된 다른 노드부터 그 자식 노드로 파고드는 검색 방법
* 모든 노드를 방문하고자 하는 경우에 이 방법을 선택
* BFS보다 좀 더 간단하지만, 단순 검색 속도 자체는 느리다.
구현 방법
스택을 사용한다.
문제
다음과 같이 리스트 형태로 노드들의 연결 관계가 주어진다고 할 때 깊이 우선 탐색으로 이 노드들을 탐색했을 때의 순서를 공백으로 구분하여 출력하세요.
graph = {'E': ['D', 'A'],
'F': ['D'],
'A': ['E', 'C', 'B'],
'B': ['A'],
'C': ['A'],
'D': ['E','F']}
사진 도식화
문제풀이
현재 정점에서 한 방향으로 가면서 검사하며, 막힌 정점은 포기하고 마지막에 따라온 간선으로 되돌아간다.
자, 이제 스택을 이용해서 탐색을 시작한다.
스택에 E가 쌓이고, E를 실행하며 Current로 이동한다.
이때 Current로 이동할때, 다음 경로인 A와 D가 Stack에 쌓이게 된다.
(이후, E는 Current에서 방문경로로 이동)
스택은 LIFO(Last In First Out) 방식으로, 쌓인 스택에서 D가 먼저 실행하며 Current로 이동하게 된다.
이 때, 다음 경로인 F가 스택에 마지막으로 다시 쌓이게 된다.
(이후, D도 방문경로로 이동하게 된다.)
스택을 통하여 이러한 노드를 계속 탐색하면 방문경로는 아래와 같이 나오며,
DFS는 이러한 방식으로 탐색을 하면 된다.
자, 이제 방식을 알았으니 코드로 구현해보자.
코드 풀이
function dfs(graph, start) {
let visited = []
let stack = [start]
// stack의 값이 다 빠져나갈 때 종료
while (stack.length !== 0) {
let n = stack.pop()
// 방문했던 상위 노드 제외 로직
if (!visited.includes(n)) {
visited.push(n)
let sub = graph[n].filter(x => !visited.includes(x))
for (let i of sub) {
stack.push(i)
}
}
}
return visited;
}
console.log(dfs(graph, 'E'))
[참고]
인프런, 제주코딩베이스캠프 Code Festival: JavaScript 100제: 모든 이미지와 풀이는 해당 강의 자료를 참고했습니다.