티스토리 뷰
DFS와 BFS
이번 포스팅에서는 DFS와 BFS에 대해서 자세히 설명하도록 하겠습니다.
DFS(Depth First Search) : 깊이 우선 탐색
DFS는 맹목적 탐색 방법의 하나로 탐색 트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식 노드를 첨가하며, 첨가된 자식 노드가 목표 노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 나가는 방식입니다.
트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식입니다. 대표적으로 백트래킹(부모 노드로 되돌아오는 과정)에 사용합니다. 일반적으로 재귀 호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 합니다. 구조상 스택 오버플로우에 유의해야 합니다.
자동 미로 생성에 많이 사용되는 알고리즘이기도 합니다. 방향은 무작위로 해서 계속 뚫다가 막혀서 못 뚫게 되면 뚫을 수 있는 곳이 발견될 때까지 되돌아가서 다시 뚫고, 또 막히면 되돌아가고 이런 식으로 무한히 반복하다 보면 생깁니다. 게다가 이 방식으로 미로를 만들면 빠져나가는 경로 또한 단 하나만 생깁니다.
DFS를 잘 이용하면 방향 있는 그래프에서 사이클(cycle)이 있는지 판단하는 것도 가능합니다. 즉 어떤 한 임의의 노드에서 길을 따라 가보면 자기 자신으로 돌아올 수 있는 경로가 있는지 확인할 수 있습니다.
장점
현 경로상의 노드들만 기억하면 되므로 저장 공간의 수요가 비교적 적습니다. 또한, 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있습니다.
단점
해가 없는 경로에 깊이 빠질 가능성이 있습니다. 따라서 실제로는 미리 지정한 임의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수 있습니다. 또한, 얻어진 해가 최단 경로가 된다는 보장이 없습니다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이 우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있습니다.
관련 문제 : DFS와 BFS(해결): https://www.acmicpc.net/problem/1260
단지 번호 붙이기(해결) : https://www.acmicpc.net/problem/2667
유기농 배추(해결) : https://www.acmicpc.net/problem/1012
BFS(Breadth First Search) : 너비 우선 탐색
BFS는 한 갈림길에서 연결되는 모든 길을 한 번씩 탐색하기 때문에 가중치가 없는 그래프에서는 시작점에서 끝점까지의 최단경로를 알아낼 수 있습니다. 또한, 맹목적 탐색 방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법입니다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용합니다.
BFS 확장 알고리즘
장점
출발 노드에서 목표 노드까지의 최단 경로 길이를 보장합니다.
단점
경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억공간을 필요로 하게 됩니다. 도한 해가 존재하지 않는다면 유한 그래프의 경우에는 모든 그래프를 탐색한 후에 실패로 끝나게 됩니다. 무한 그래프의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못합니다.
관련 문제 : DFS와 BFS(해결) : https://www.acmicpc.net/problem/1260
출처 : https://namu.wiki/w/DFS, swexpertacademy.com