DFS, BFS의 개념과 동작방식

DFS: depth first search의 약자로 "깊이 우선 탐색"을 뜻한다.

보통 dfs, bfs는 트리 혹은 2차원 좌표상에서 구현하게 된다. 

 

탐색 조건에 맞다면 탐색 가능할때까지 쭈욱 가는게 dfs이다. 

탐색 조건이라는게 뭘까?

어떤 상황에서 구현하느냐에 따라 다르겠지만 필수적인 탐색조건은 이전에 방문했는지 여부이다. 

 

그 외에도 2차원좌표상에서 구현한다면 좌표범위를 벗어나지 않는지, 

트리상에서 구현한다면 리프노드를 벗어나지 않는지 등이 있다. 

이외에도 상황별로 여러가지 조건이 추가 될 수 있다. 

 

보기 쉽게 2차원 배열에서 dfs를 구현해보자.

만약 (3,3)의 2차원 좌표상에서 dfs를 (상, 우, 하, 좌)의 방향대로 탐색을 가정하면 다음과 같은 결과가 나오게된다.

 

3,3에서의 탐색시작시 결과

 

그렇다면 dfs를 어떻게 구현할까? 구현코드를 알아보자 

 

 

dfs는 재귀함수를 이용한 방법, stack을 이용한 방법이 있는데 보통 재귀가 간결하기때문에 재귀함수를 이용한다. 

 

재귀를 이용한 dfs는 다음과 같은 순서로 동작을 하게된다. 

1) dfs함수의 파라미터로 초기 탐색을 시작할 지점이 들어오게 된다. 

2) 이 지점을 visit배열을 이용하여 방문처리를 한다

3) 이후에 for문에 들어가 지정해놓은 방향(이 경우에는 사방탐색)대로 탐색 가능성을 파악한다. (visit여부, 배열범위)

4) 이전에 방문하지도 않았고 범위 내에도 있다면 dfs함수를 호출(재귀호출)하여 탐색을 한다.

 

이 과정을 계속 반복하게 된다. 

 

 

 

 

 

 

BFS: breadth first search의 약자로 "넓이 우선 탐색"을 뜻한다.

기본적인 조건(범위를 벗어나면 안되고 방문한 곳은 또 재방문하지 않는다) 은 dfs와 같다. 

탐색 방법에서의 차이가 있는데 갈 수 있을때까지 가는 dfs와 달리 bfs는 방문한 곳을 기준으로 

내 주변에 있는것들부터 방문한다.

즉, 방문하지 않았을때 방문 가능한것들을 미리 방문예약을 해놓고 그 순서에 맞게 방문을 한다고 보면 된다. 

이러한 탐색을 하기 위해 큐라는 자료구조를 사용하게 된다.

 

 

BFS 탐색을하면 다음과 같은 결과가 나오게 된다. 

(3,3)시작기준 BFS의 방문 단계

 여기서 같은 숫자로 표시된 부분들은 (3, 3)을 기준으로 같은 넓이에 있다고 보면 된다. 

이 순서는 상황에 따라 어떻게 정하느냐에 따라 달라질 수 있다. 

 

 

 

1) bfs함수의 파라미터로 시작점이 들어오고 시작점을 큐에 넣고 큐가 while문을 돌게된다. 

2) while문 안에서 큐의 제일 앞에 있는 것(좌표)를 빼낸다. 그것을 기준으로 for문을 돌린다.

3) for문에서 사방탐색을 하며 조건에 맞는 좌표들은 visit처리를 하고 큐에 넣게된다. 

 

모든 좌표를 탐색할때까지(큐가 비어있기 전까지) while문에서 탐색을 진행하게 된다.

 

BFS와 DFS의 동작방식을 보면 우선탐색기준(넓이? 깊이?) 외에도 큰 차이점이 있다. 

바로 방문처리 시점인데 이 부분을 잘 이해해야 헷갈리지 않고 사용할 수 있다.

이 부분에 대해서는 다음 글에서 알아보도록 한다.