DFS(Depth-First Search) 알고리즘
DFS란?
- 그래프 또는 트리를 탐색하며 깊은 단계를 우선적으로 선택하여 최대한 깊게 탐색하는 알고리즘이다. 주로 재귀와 스택을 이용하여 구현하며 상세한 알고리즘에 따라 다를 수 있지만, 방문한 곳을 표시하지 않으면 무한루프 등에 빠질 수 있는 위험이 있다.
- 완전탐색의 일종이며, 백트래킹이 없을 시 굉장히 많은 시간을 소모할 수 있다.
- 대표적 예시로 미로탐색과 경우의 수 문제가 있다.
DFS의 작동원리
1. 중복방문을 체크할 visited 배열과 시작 노드를 선정한다.
- node = 1, visit = []
2. 현재 노드와 연결된 노드를 찾고, 연결된 노드 중 하나로 다시 dfs를 실행한다. 이 때, 방문한 노드는 visit 배열에 기록한다.( 이, 때 연결된 남은 노드를 나중에 보고 현재 노드랑 연결된 곳에 가장 깊이 들어가는 것이 dfs 알고리즘이다.)
- node = 1, 연결된 node = 2,5,3, visit = [1]
3. 가장 깊은 곳 까지 탐색을 진행한다.
- node = 2 연결된 node = 4,6, visit = [1,2]
- node = 6 연결된 node = , visit = [1,2,6]
6은 최대 깊이로 가서 더 이상 연결된 게 없으므로, 이전 노드로 돌아간다.
- node = 2 연결된 node = 4,6, visit = [1,2,6]
2는 연결된 노드가 4,6이 있는데 6은 이미 방문했으므로 4를 방문한다.
- node = 4 연결된 node = visit = [1,2,6,4]
마찬가지로, 4는 연결된 node가 없어서 이전 node 2로 돌아가고 이전 node 2는 모든 node를 방문했으므로, 다시 이전 노드 1로 돌아간다.
- node = 1, 연결된 node = 2,5,3, visit = [1,2,6,4]
5는 방문하지 않았으므로, 5부터 시작하며 이 과정을 반복하여 모든 node를 방문하면(vist안에 모든 노드가 들어가면) dfs를 종료한다. 이 과정에서, 목적이 모든 node 방문이 아닌 6 찾기 등이면 이를 백트래킹으로 설정해두면 그 외 과정 은 진행되지 않고 생략할 수 있다.
DFS 코드
위 설명은 재귀적으로 설명한 dfs이다. dfs는 흔히 stack을 이용한 반복문과 재귀문으로 구현할 수 있다.
// 노드의 개수,
// 노드간의 연결관계(인접행렬),
// 방문여부 확인 visited,
// 방문 순서를 프린트할 order
const n = 7
const adj = [[0,1,1,0,1,0,0],[0,0,0,1,0,1,0],[0,0,0,0,0,0,1],[0,0,0,0,0,0,0],[0,0,0,1,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0]]
const visited = {}
const order = []
// dfs logic by rec
function dfs(node) {
visited[node] = 1
order.push(node)
for (let i=0; i<n; i++){
if (adj[node][i] === 1 && !visited[i]){
dfs(i)
}
}
}
dfs(0)
console.log(order) // [ 1, 2, 4, 6, 3, 7, 5 ]약간 순서가 다르지만, 위랑 비슷하게 진행된 것을 볼 수 있다.
const n = 7
const adj = [[0,1,1,0,1,0,0],[0,0,0,1,0,1,0],[0,0,0,0,0,0,1],[0,0,0,0,0,0,0],[0,0,0,1,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0]]
const visited = {}
const order = []
// dfs logic by loop
const stack = []
stack.push(0)
while (stack.length > 0){
const node = stack.pop()
if (!visited[node]) {
visited[node] = 1
order.push(node)
}
for (let i=0; i<n; i++){
if (adj[node][i] === 1 && !visited[i]){
stack.push(i)
}
}
}
console.log(order) // [1, 5, 4, 3, 7, 2, 6 ]이 코드는 결과가 많이 다르다. 그 이유는 시작되는 노드들이 다르기 때문이다. 재귀코드는 1다음 바로 2로 들어가서 dfs가 진행되지만, 반복문 코드는 5로 들어가서 dfs가 진행된다. 코드를 짜는 방식에 따라서 조금씩 다른 결과가 나올 수 있다.