알고리즘 & 자료구조 복기글 (2) - BFS 와 DFS

BFS 와 DFS는 정말 노드와 간선이 있으면 어디에서든 쓰일 여지가 있는 알고리즘이다. 정확히 말하자면 탐색방법이다.

BFS는 Breadth First Search의 약자로 한국어로는 넓이 우선 탐색이다. 말 그대로 넓이를 우선시 하는 탐색 방법이다.
DFS는 Depth First Search의 약자로 한국어로는 깊이 우선 탐색이다. 역시 말 그대로 깊이를 우선시 하는 탐색 방법이다.

BFS 와 DFS를 처음 공부할때는 뉴비인 경우가 많기 때문에 보통은 바로 트리나 그래프를 그리기 전에 예시를 든다. 보통은 이러한 예시를 든다.
'우리가 만약 넓고 좋은 새 집을 보러간다고 하자. BFS는 처음 들어선 거실에서 연결된 방을 다 가보는 것이다. 여러 방들을 둘러보면, 그제서야 보았던 방 중 하나를 기억해서 그 방에 연결된 배란다나 화장실을 보는 것이다. 이와 반대로 DFS는 처음에 들어서면 한 방을 골라 들어간뒤 그 방에 연결된 화장실로 들어가서 그 안의 욕조까지 본 뒤 더 이상 들어갈 수 없으면 나와서 그 옆의 베란다로 들어가는 방식이다.'

사실 아는 입장에서 보면 무엇을 이야기 하는지 알겠는데 굳이 이래야 하나 싶을 수도 있고 처음보는 입장에서는 이게 무슨소린지 싶을 수 있다. 하지만 탐색을 할때 무엇을 우선지 하는지는 어느 정도 감이 잡혔을 수도 있다. 

그러면 제대로 설명을 해보자. 

다음과 같은 트리에서 생각을 해보자.

BFS

A에서 시작을 하게 되면 A와 연결된 B와 C를 다음으로 탐색을 하게 된다. 그 다음은 B에서 시작하여 이미 방문을 한 A를 제외하고 D, E를 탐색하고, C를 기준으로 방문한 A를 제외하고 F를 탐색한다. 그리고 D를 기준으로 G 를 탐색하고, EFG 기준으로 탐색하려고 하지만 할것이 없어 종료된다. 전체적인 순서를 나열하면 A->B->C->D->E->F->G.

DFS

A에서 시작을 하여 연결된 곳 중 탐색안한 B를 간다. B에서 연결된 곳 중 안 한 D를 간다. D에서 연결된 곳중 탐색을 안한 G를 간다. 더 이상 탐색할 곳이 없으므로 다시 D로 올라가고 D에서도 갈 수 있는 곳이 없으므로 B로 올라간다. B에서 E 를 탐색하고 A로 올라간후 똑같이 A->C->F를 갔다가 다시 올라와서 A에서도 들어갈 곳이 없으므로 종료한다. 전체적인 순서를 나열하면 A->B->D->G->E->C->F.

구현 방식

구현은 보통 BFS는 큐, DFS는 재귀를 사용한다. 공통적으로 인접한 곳을 모두 돌면서 vis배열에 체크 안된 곳을 다음 순서로 이용한다. 따라서 당연히 방문한 정점은 vis배열에 체크를 해 주어야 한다. BFS는 방문한 정점을 큐에 넣고 큐에서 하나씩 빼면서 조건을 만족하는 정점들을 다 방문해주는 방식으로 하면되고, DFS는 모든 점을 방문하는 과정인 반복문 안에서 방문할 점이 발견될 때마다 재귀로 넘겨주면 된다. 

시간복잡도는 둘 다 O(V+E)

추천 문제

https://www.acmicpc.net/problem/tag/BFS 와 https://www.acmicpc.net/problem/tag/DFS 문제들을 윗 부분부터 조금씩 풀어보는 것이 자신의 코드 확립과 초반 문제에서의 쓰이는 방향을 잡는데에 도움이 될 것이다. 자신이 코드를 쉽게 짤 수 있으면 된다. 어짜피 내가 찾아서 풀려고 안해도 나중에 결국 많은 곳에서 이용하게 된다. 

코드

코드는 가장 기초적이면서도 이야기하기 쉬운 https://www.acmicpc.net/problem/1260를 가지고 다음 포스팅을 작성할건데, 이 블로그에 올라올 코드는 현재 사용하고 있는 많이 정제된 코드이다. 만약 어떻게 돌아가는지 전반적으로 알기 쉬운 코드를 찾는다면 bfs,dfs 코드는 많으니 다른 코드를 보는것이 좀 더 도움이 될 수도 있다.