[코드트리] DFS / BFS

소마 서류에 덜컥 붙어버리고, 코테 준비 4일전사 도전...

자주 나온다는 유형을 급하게 공부해봅니다 하하

 

---

DFS는 Depth First Search, 깊이 우선 탐색입니다.

이름처럼 최대한 깊게 탐색한 후 더 이상 도달할 수 없는 상황이라면 다시 이전으로 돌아갑니다.

중요한 것은 깊게 탐색하고 나서 이전과정으로 돌아가야 한다는 점 입니다.

 

 DFS는 재귀(스택)를 활용해 구현하는 경우가 많습니다. 즉, 방문할 수 있는 지점이 있다면 그 지점을 방문하는 함수를 재귀적으로 호출하고, 더 이상 방문할 곳이 없다면 함수를 종료하면 될 것입니다.

 

다만, 이미 방문했던 지점을 또 방문하면 효율이 떨어지기 때문에 이전에 방문했던 지점은 다시 방문하지 않아야 합니다.

한 번 방문한 지점은 어떤 처리를 해서 더 이상 방문하지 않도록 막아야 한다는 것입니다.

그래서 우리는 visited라는 배열을 하나 만들고, 그 번호의 지점을 방문한 적이 있는지 확인하며 진행해야 합니다.

 

DFS 예시코드 (ㅊㅊ 코드트리)

 

 

BFS는 Breadth First Search, 너비 우선 탐색입니다.

재귀(스택)을 활용했던 DFS와 달리, BFS는 큐를 사용합니다.

하나의 노드에 방문하게 되면, 그 노드와 인접한 노드 중 방문한 적이 없는 다른 노드를 모두 큐에 넣습니다.

우리는 큐가 FIFO 구조라는 것을 알기 때문에, 이런식으로 넣게 되면 이후엔 처음 넣었던 노드의 이웃 노드를 순차적으로 방문하게 될 것입니다.

 

자연스럽게 이후에는 각각의 이웃들을 큐에 넣게 될텐데, 이런식으로 진행되면

시작 노드의 이웃 -> 그 다음 노드의 이웃 -> 그 다음 다음 노드의 이웃

순으로 방문하게 될 것입니다. 즉, 시작점을 기준으로 가장 가까운 정점부터 방문하게 되는 것입니다.

 

BFS 과정 예시 (출처 코드트리)

 

 

그렇다면 DFS와 BFS의 성능 차이는?

결론만 말하면 이론적으론 별 차이 없다고 합니다.

 

어차피 모든 노드와 엣지를 방문하는 것이기 때문에 시간복잡도 자체는 O(∣V∣+∣E∣)로 동일합니다.

그러나 실제로 코드를 짜게되면 DFS가 약간 느린 편인데, 그 이유는 재귀함수의 오버헤드(함수 실행 시 발생하는 시간 지연) 때문입니다.

하지만 큰 문제는 없기 때문에, 상황에 따라 더 편한 알고리즘을 선택해서 사용하면 됩니다.

 

보통 최단거리를 구하는 문제에는 BFS를 사용합니다.

BFS는 정의상 시작점으로부터 가까운 지점부터 방문하게 되기 때문에

가중치가 전부 동일한 그래프에서는 최단거리를 확실하게 구해줄 수 있는 것입니다.

 

 

출처 코드트리