# 시작
자바스크립트 알고리즘 스터디에서 주는 과제에 프로그래머스 "여행 경로" 문제가 있다. 그래서 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)
Plain Text
복사
# 잡설
위의 수도코드는 확 와닿지 않는다.. 아래처럼 그림으로 이해하는 건 자료구조, 알고리즘 시간에 접해서 굉장히 이해하기 쉬웠다. 하지만 코드화해야하니...
# 그림 설명
DFS 그림 설명
# DFS 장점
•
현 경로상의 노드를 기억하기 때문에 적은 메모리 사용
•
찾으려는 노드가 깊은 단계에 있는 경우 BFS보다 빠르다.
# DFS 단점
•
해가 없는 경로를 탐색할 경우 단계가 끝날 때까지 탐색합니다. 효율성을 높이기 위해서 미리 지정한 임의 깊이까지만 탐색하고 해를 발견하지 못하면 빠져나와 다른 경로를 탐색하는 방법을 사용한다.
•
DFS를 통해서 얻어진 해가 최단 경로라는 보장이 없다. DFS는 해에 도착하면 탐색을 종료하기 때문이다.
# DFS vs BFS 차이
문제에 적용하기 위해서 어떤 필요한 정보인 것 같아 BFS를 다시 정리하기 전에 미리 알아본다.
•
DFS는 스택(or 재귀)를 사용한다. BFS는 큐를 사용한다. => 여행 경로 문제에서는 스택을 사용할 것이다.
•
BFS는 재귀적으로 동작하지 않는다.
문제를 푸는 입장에서는 다음과 같은 구분점을 알아야 한다.
•
최단 거리 문제를 푼다면 BFS 사용
•
이동할 때마다 가중치가 붙어서 이동한다거나 이동 과정에서 여러 제약이 있을 경우 DFS가 좋다.
백준 문제
백준 추천 문제(dfs, bfs)
# 참고
