[c++] BFS, DFS(너비 우선 탐색. 깊이 우선 탐색)

1. 그래프에서 탐색

알고리즘 문제를 풀다보면 많은 그래프들을 마주하게 된다. 대표적인 예가 미로에서 최단거리를 찾는 문제나 연결되어 있는 컴포넌트를 찾는 문제에서이다. 

우리는 이렇게 그려져있거나 가상의 그래프를 탐색해야하는데 컴퓨터는 일정한 알고리즘에 의해 이러한 그래프들을 탐색한다. 그 중 대표적인 예가 DFS(깊이 우선 탐색 Depth-First-Search)와 BFS(Breadth-First-Search 너비 우선 탐색)이다. 

 

2. DFS (깊이 우선 탐색)이란? 

출처: https://developer-mac.tistory.com/64

그래프가 위와 같이 존재할 때 다음 분기로 넘어가기전 해당 분기를 완벽하게 탐색한 후 넘어가는 탐색 방식이다. 위의 그림을 보면 한 번 이동한 줄기의 마지막에 도착할 때까지 그 분기를 탐색한 후 다음 분기로 넘어가는 것을 확인할 수 있다. 

시간 복잡도

• 인접 리스트 : O(V + E)
• 인접 행렬 : O( V^2)

DFS에서 중요한 것은 탐색방향이다. 나는 상하좌우를 탐색한다고 가정한 DFS를 c++를 이용하여 구현해보았다. 

int dy[4] = {1, 0, -1, 0};
int dx[4] = {0, 1, 0, -1};

int x, y; // 현재 탐색하고 있는 x, y좌표
int ny, nx;// 다음에 탐색할 x, y좌표


void dfs(int y, int x){
	visited[y][x] = 1;
	for(int i=0;i<4;i++){
		ny = y + dy[i];
		nx = x + dx[i];
		if(ny<0||ny > 51 || nx < 0 || nx> 51)continue;
		if(a[ny][nx] == 1 && visited[ny][nx] == 0){
			dfs(ny, nx);
		}
	}
	return;
}

DFS를 살펴보면 우선 현재 탐색하고 있는 인덱스와 다음에 탐색할 인덱스를 정의해주고 그 후 방문 배열을 만들어 이미 방문한 인덱스에 대해 방문처리를 해준다. 그 후 재귀함수를 통해 다음에 방문할 인덱스를 전달해주면 간단하게 구현이 가능하다. 

 

3. BFS(너비 우선 탐색)이란?

출처: https://developer-mac.tistory.com/64

그래프가 위와 같이 존재할 때 한 노드의 존재하는 모든 분기들을 완벽하게 탐색한 후 다음 레벨로 넘어가는 탐색 방식이다. 위의 그림을 보면 하나의 노드에 존재하는 모든 분기들을 다 탐색하고 다음 레벨로 넘어가는 것을 볼 수 있다. 

 

시간 복잡도

• 인접리스트: O(V+E)
• 인접 행렬 : O(V^2)

BFS는 일반적으로 queue자료구조를 이용해서 구현한다. queue자료구조는 FIFO(First In First Out) 즉 들어간 순서대로 나오는 자료구조로 BFS에서는 다음에 탐색할 인덱스를 queue에 저장해두었다가 모든 분기를 탐색하는 것이 끝이나면 다음 레벨로 넘어가 방문 처리를 한다. 

c++로 BFS를 구현하면 다음과 같다. 

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

queue<pair<int, int>> q; // q설정
    visited[0][0] = 1;// 방문 정보를 넣는다. 
    q.push({0,0});
    while(q.size()) // q의 사이즈만큼 반복 q의 사이즈는 하나의 노드의 유의미한 분기의 수와 같다. 
    {
        tie(y,x) = q.front(); q.pop();
        for(int i =0; i < 4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || ny > n || nx < 0 || nx > m || a[ny][nx] == 0) continue; // 경계조건과 0일 경우
            if(visited[ny][nx]) continue;// 방문을 이미 한 경우
            visited[ny][nx]  = visited[y][x] + 1;
            q.push({ny, nx});

        }
    }

 앞서 dx와 dy는 상하좌우의 direction배열로 x좌표의 경우 상->우->하->좌 시계방향으로 돌렸을 때 x좌표는 기준 노드로 부터 0 1 0 -1이 되기 떄문이고 dy또한 같은 방식으로 1 0 -1 0이 된다. 

또한 while문 안에서 q.size()만큼 반복하는 이유는 한 노드의 모든 분기를 탐색한 후 넘어가야하기 때문이다. while문 안에서 for문을 돌며 기준 노드의 상하좌우를 돌면서 조건에 부합하는 다음 노드를 찾고 그 노드를 다시 queue에 push하는 방법이다.