DFS란? What is DFS?

# 시작

자바스크립트 알고리즘 스터디에서 주는 과제에 프로그래머스 "여행 경로" 문제가 있다. 이 문제를 풀려고 했는데 이 문제는 dfs를 기본적으로 알아야된다는 것을 알게 되었고 지금까지 dfs를 이용해서 문제를 제대로 풀어본 적이 없었다. 그래서 dfs 이론부터 다시 공부하면서 풀어보려고 정리하였다.

# DFS(깊이 우선 탐색)란?

DFS는 미로 탐색과 같다. 미로에서 끝이 나올 때까지 깊이 들어가는 것처럼 DFS 또한 더 깊이 들어갈 수 없을 때까지 탐색한다.

# 구현

Step 1 : 스택에 시작 노드를 넣는다.

Step 2 : 스택이 비어 있으면 실행을 멈추고 False를 반환한다.

Step 3 : 스택의 맨 위 노드가 찾고자 하는 노드라면 탐색을 종료하고 True를 반환한다.

Step 4 : Step 3 에서 스택의 맨 위 노드가 찾고자 하는 노드가 아니라면 해당 노드를 POP한다.

(스택에 들어온 적이 없는) POP한 노드의 모든 이웃 노드를 찾아서 순서대로 스택에 넣는다.

Step 5 : Step 3으로 돌아간다.

# Pseudo Code

DFS(G, u)
    u.visited = truefor each v ∈ G.Adj[u]
        if v.visited == false
            DFS(G,v)

init()
    For each u ∈ G
        u.visited = falseFor each u ∈ G
       DFS(G, u)

# 잡설

위의 수도코드는 확 와닿지 않는다.. 아래처럼 그림으로 이해하는 건 자료구조, 알고리즘 시간에 접해서 굉장히 이해하기 쉬웠다. 하지만 코드화해야하니...

# 그림 설명

DFS 그림 설명

# DFS 장점

현 경로상의 노드를 기억하기 때문에 적은 메모리 사용

찾으려는 노드가 깊은 단계에 있는 경우 BFS보다 빠르다.

# DFS 단점

해가 없는 경로를 탐색할 경우 단계가 끝날 때까지 탐색합니다. 효율성을 높이기 위해서 미리 지정한 임의 깊이까지만 탐색하고 해를 발견하지 못하면 빠져나와 다른 경로를 탐색하는 방법을 사용한다.

DFS를 통해서 얻어진 해가 최단 경로라는 보장이 없다. DFS는 해에 도착하면 탐색을 종료하기 때문이다.

# DFS vs BFS 차이

문제에 적용하기 위해서 어떤 필요한 정보인 것 같아 BFS를 다시 정리하기 전에 미리 알아본다.

DFS는 스택(or 재귀)를 사용한다. BFS는 큐를 사용한다. => 여행 경로 문제에서는 스택을 사용할 것이다.

BFS는 재귀적으로 동작하지 않는다.

문제를 푸는 입장에서는 다음과 같은 구분점을 알아야 한다.

최단 거리 문제를 푼다면 BFS 사용

이동할 때마다 가중치가 붙어서 이동한다거나 이동 과정에서 여러 제약이 있을 경우 DFS가 좋다.

🍧 백준 문제

백준 추천 문제(dfs, bfs)

# 참고

covenant.tistory.com/132