프로그래머스 문제를 풀며 DFS나 BFS 개념을 요구하는 문제들이 있어 개념을 한 번 정확하게 짚고 넘어가야겠다 싶어 오늘은 DFS와 BFS에 대해 정리해보려고 한다.
깊이 우선 탐색 (DFS)
깊이 우선 탐색은 그래프의 한 경로를 끝까지 탐색 후 다음 경로를 탐색하는 방식의 알고리즘이다. 깊이에 중점을 두고 탐색하며 탐색 과정에서 방문한 노드를 방문한 노드로 표시하여 다시 방문하지 않도록 한다.
✨ 더 이상 탐색할 노드가 없을 때까지 하나의 경로를 완전히 탐색한다.
노드는 그래프에서의 데이터 요소를 나타내며, 이들 간의 관계를 표현하는 데 사용된다.
DFS의 알고리즘 단계
- 시작 노드를 스택에 넣는다.
스택은 데이터를 저장하는 선형 자료구조로, 후입선출(LIFO)의 원칙에 따라 동작한다. (가장 나중에 쌓은 책을 먼저 꺼낼 수 있다는 개념) - 스택에서 노드를 하나 꺼내고, 해당 노드를 방문한다.
- 해당 노드의 인접 노드 중 방문하지 않은 노드가 있다면 그 노드를 스택에 넣고 방문했다고 표시한다.
- 방문하지 않은 인접 노드가 없을 때까지 스택의 작업을 반복한다.
너비 우선 탐색 (BFS)
너비 우선 탐색은 그래프의 노드를 레벨 순서대로 탐색하는 방식의 알고리즘이다. 시작점이자 루트 노트로부터 인접한 모든 노드를 먼저 방문한 후에 그 다음 레벨의 노드를 방문한다. 이 과정을 반복하여 모든 노드를 탐색한다.
BFS에서 레벨은 특정 노트로부터 시작하여 도달할 수 있는 경로의 길이를 의미한다.
즉, 루트 노드를 포함한 한 단계의 깊이를 나타낸다.
BFS의 알고리즘 단계
- 시작 노드를 큐에 넣는다.
큐는 FIFO의 원칙에 따라 동작하여 시작 노드가 큐의 끝에 추가된다. - 큐에서 가장 먼저 들어온 노드를 하나 꺼내어 방문하며 이것이 현재 처리중인 노드가 된다.
- 현재 처리 중인 노드와 연결 된 모든 인접 노드를 방문하며 방문되지 않은 인접 노드를 큐에 넣고 방문했다고 표시 한다.
- 큐에 더 이상 방문하지 않은 노드가 없을 때까지 위 과정을 반복한다.
DFS와 BFS는 언제 사용될까?
깊이 우선 탐색인 DFS는 특정한 경로를 따라 최대한 깊이 들어가서 탐색하고자 할 때 사용되며 해를 빠르게 찾는 것이 목표가 아닌 경우에 사용된다.
예를 들어☝🏻 미로 찾기와 같이 미로 내에서 출발점에서 도착점까지의 경로를 찾을 때, 게임 트리 탐색과 같이 보드 게임이나 퍼즐 게임에서 가능한 모든 수를 시도해보고자 할 때 사용될 수 있다.
너비 우선 탐색인 BFS는 최단 경로를 찾거나 최소 비용 경로를 찾을 때 사용되며 최단 경로를 찾는 문제나 노드 간의 최소 거리를 구하는 문제에 적합하다.
예를 들어☝🏻 네트워크 최단 경로, 지도에서 최단 경로 탐색 등에 사용될 수 있다.
DFS와 BFS의 장단점
- 깊이 우선 탐색인 DFS의 장점
- 한 경로를 깊이 탐색하므로 미로 탐색과 같은 문제에서 더 빠른 속도를 보일 수 있다.
- 깊이를 우선으로 탐색하기에 현재 경로에 관련된 정보만을 저장하므로 메모리 사용이 BFS에 비해 적을 수 있다.
- 깊이 우선 탐색인 DFS의 단점
- 최단 경로를 찾는 데 적합하지 않다.
- 그래프가 순환 구조일 경우 무한 루프에 빠질 수 있으므로 방문한 노드를 체크하여 무한 루프를 방지해야 한다.
- 순환 구조란 자기 자신으로 되돌아가는 경로가 존재하는 구조를 말하는데, DFS에서 순환을 발견하면 계속해서 해당 경로를 따라가며 순환을 반복하는 과정을 진행하게 된다.
따라서, DFS는 순환 구조를 만나면 끝나지 않는 상태로 남게 되어 해당 경로를 끝까지 탐색하지 않기에 무한 루프에 빠질 수 있다.
- 너비 우선 탐색인 BFS의 장점
- 시작 노드에서부터 레벨 순서대로 탐색하기에 최단 경로를 먼저 찾을 수 있다.
- DFS와 달리 모든 인접 노드를 우선 탐색하므로 무한 루프에 빠질 염려가 없다.
- 너비 우선 탐색인 BFS의 단점
- 모든 방문한 노드를 큐에 저장해야 하므로 메모리 사용량이 많을 수 있다.
