[개념] DFS/BFS

DFS/BFS 란

DFS/BFS는 그래프를 순회할 때 사용되는 방법이다.

DFS는 Depth-First Search, 깊이우선탐색이라는 뜻이고,

BFS는 Breadth-First Search, 너비우선탐색이라는 뜻이다.

 

DFS는 한 정점에서 연결되어 있는 정점 중 한 정점을 우선적으로 방문한다.

즉, 이미 방문한 정점이 나올 때까지 최대한 깊게 방문한다.

 

반대로 BFS는 한 정점에서 연결되어 있는 모든 정점을 차례로 방문한다.

 

DFS/BFS 구현

DFS는 재귀를 활용해서 구현하는 것이 편리하다.

더 방문할 정점이 없을 때 뒤로 돌아가서 방문할 다른 정점은 없는지 탐색하는데

재귀를 이용하면 이를 자연스럽게 구현할 수 있다.

 

BFS는 큐를 활용해서 구현하는 것이 편리한데,

인접한 정점들을 큐에 넣고 저장해야 순차적으로 정점들을 접근할 수 있기 때문이다.

큐를 사용하지 않으면 인접하지 않은 정점보다 인접한 정점을 먼저 방문할 방법이 없다.

 

C++로 구현한 DFS/BFS는 아래와 같다. 알고리즘 문제를 풀 때는 아래 형식을 따라서 문제를 해결하면 수월하다.

 

DFS/BFS의 시간복잡도

DFS/BFS 각각의 시간복잡도는 그래프 표현 방식에 따라 달라진다...