DFS를 가볍게 알아보자
🥯 DFS 란?
DFS는 Depth First Search의 약자로, 깊이 우선 탐색이라는 뜻을 가진 그래프 탐색 기법입니다.
DFS는 시작 노드부터 탐색을 시작하면 가던 방향으로 탐색할 노드가 없을 때까지 쭉 탐색합니다.
탐색할 노드가 없다면 나눠져 있던 갈래까지 다시 올라와서 다음 분기를 똑같이 탐색합니다.
예를 들어, 미로의 탈출구를 찾는다고 했을 때, 한 길로 이동하다가 양 갈래 길을 만났습니다.
그 때, 일단 오른쪽 길로 쭉 이동합니다. 그런데 그 길은 막혀있는 길 이었습니다.
그래서 다시 아까 그 양 갈래 길로 이동해서 왼쪽 길로 이동합니다.
DFS는 이런 느낌이라고 할 수 있습니다.
특징
- 노드를 방문하고 방문 체크를 해주어야 합니다. 하지 않으면 무한 루프에 빠질 수 있습니다.
- 단순 탐색 시간은 DFS와 비슷한 BFS에 비해 느립니다.
따라서 최단 거리를 구해야 하는 문제에는 적합하지 않습니다. - 하지만 BFS에 비해 비교적 간결한 코드 작성이 가능합니다.
시간 복잡도
인접 리스트로 구현했을 경우: O( | V | + | E | )
V: 정점의 개수, E: 간선의 개수
DFS는 최악의 시나리오에서 그래프의 모든 정점과 간선을 한 번 방문하기 때문입니다.
일반적으로 DFS의 시간복잡도는 그래프의 정점과 간선의 수로 표현되는 입력 크기에 선형적입니다.
인접 행렬로 구현했을 경우: O( | V | ^ 2 )
V: 정점의 개수
이는 모든 정점에 대해 DFS가 다른 모든 정점을 검사하여 그들 사이에 가장자리가 있는지 확인해야 하기 때문입니다.
따라서 n개의 정점이 있는 그래프의 경우 인접 행렬에는 n^2개의 요소가 있으며 DFS는 검색을 수행하기 위해 이러한 각 요소를 검사해야 합니다.
인접 행렬은 그래프를 나타내는 간단하고 편리한 방법이지만, 간선이 적은 그래프라면 비효율적인 알고리즘이 될 수 있습니다.
🍖 DFS의 동작 과정
- 1번 노드를 시작 노드로 하여 탐색 시작, 방문 확인, 스택에 push 합니다.
- 2번 노드를 방문한 적이 없으니 탐색, 방문 확인, 스택에 push 합니다.
- 6번 노드를 방문한 적이 없으니 탐색, 방문 확인, 스택에 push 합니다.
- 더 이상 탐색할 노드가 없으니 스택 최상단에 있는 6번 노드를 삭제하고, 최상단에 있는 2번 노드로 되돌아갑니다.
- 2번 노드에서 다음으로 탐색할 수 있는 4번 노드로 이동합니다.
- 4번 노드를 방문한 적이 없으니 탐색, 방문 확인, 스택에 push 합니다.
- 이 과정을 더 이상 노드를 탐색할 수 없을 때까지 반복합니다.
- 탐색 결과 1 2 6 4 5 3 7 순서로 탐색이 완료됩니다.
🍨 마무리
부족하고 또 부족한 글 읽어주셔서 감사합니다.
그래도 다음에 또 오세요.