[알고리즘/개념/완탐] BFS,DFS

BFS,DFS 유명한 알고리즘 주제 중 하나이다. 하지만, 처음 공부를 해보면 상당히 뜬금없는 내용으로 느껴질 수도 있다. 왜냐하면, 두가지 이론 모두 '그래프 탐색' 방법 중 하나로써 소개가 된다. 분명히 그래프를 탐색해야하는데, 알고리즘은 문제가 대부분 2차원 배열로 나오는 차이가 존재하기 때문이다.

BFS,DFS에서 헷갈릴 수 있는 포인트가 많기 때문에, 기록으로 남겨두려고 한다.

그래프에서의 BFS

BFS는 그래프를 탐색하는 방법 중 하나이다. BFS는 탐색하는 모양을 보고 '너비우선탐색'이라고 이름이 붙었다. 하지만, 내가 생각하는 BFS는 각 순간마다 모든 다음 수를 생각해보기라고 할 수 있다.

BFS를 처음으로 만든 분이 이 소리를 듣는다면 어이없으실 수 있지만, 오목으로 예를 들어보자.

이때, BFS오목기사든 DFS 오목기사든 상대방이 어디다 두는지는 생각을 하지 않는다.(??)

BFS 생각밖에 못하는 오목기사가 있다고 가정을 해보자. 이 사람의 뇌에는 BFS밖에 없다.
그렇다면, 왼쪽과 같은 상황일 때, BFS를 잘하는 사람은 아래 그림과 같이 생각을 하는거다.

내가 다음에 어디다 둘지 다음 "한 수"만 생각하는거다. 정확히는, 다음 한수를 두는 모든 경우를 살펴보는게 BFS라고 할 수 있다. 생각이 뻗어나가는 과정이 마치, 음파처럼? 퍼져나가게 되는데, 탐색하는 순서도 마찬가지로 한 수 한수 퍼져나가게 되니까 '너비 우선 탐색'이라는 말이 붙었다.

그래프에서의 DFS

DFS 또한 그래프를 탐색하는 방법 중 하나이다. DFS는 탐색하는 모양을 보고 '깊이우선탐색'이라고 이름이 붙었다. 하지만, 내가 생각하는 DFS는 각 순간에 대해 경우의 수를 정해놓고, 다음 순간을 생각하고, 그 다음 순간을 생각하고, 그 다음 순간을 생각하는 것라고 할 수 있다.

솔직히, 내가 말을 했지만 무슨 말을 했는지 잘 모르겠다. 똑같은 예제로 ,이번에는 DFS적으로 생각하는 오목기사님을 불러보자. DFS적으로 생각하는 오목기사님은 아래와 같이 한 경우에 대해서 정한 뒤, 그 다음 경우의 수를 계속 생각하는 과정을 거치게 된다.

즉, 그래프가 있다면 한 경우에 대해서 깊이 쭉 탐색한 다음, 다시 처음으로 돌아와서 다음 경우에 대해서 쭉 탐색하는 생각방법이 DFS이다.

이걸 왜 알려줌?

위의 상황을 이야기한 이유는, 문제를 읽을 때 뭔가 정해진 한 경우가 일어나고 -> 다음 경우가 일어나고 -> 다음경우가 일어나는 문제를 검색해야할 것 같은 건 DFS로 하는게 유리하다. 하지만, 한 경우에대해 발생할 수 있는 모든 경우를 다 탐색해야할 것 같은 문제는 BFS로 구현하는 것이 유리한 경우가 있기 때문이다.

DFS든 BFS든 둘 다 완전탐색 알고리즘이다.

하지만, 놀랍게도 둘 다 완전탐색 방법이기 때문에 뭘로 풀어도 상관없는 경우가 대부분이다. 하지만, 위의 생각을 갖고 있다면 좀 더 유연한 사고의 확장이 일어날 수 있기 때문에 말은 했던 것이다. 단순히 탐색을 위한 문제라면, BFS로 풀리는건 DFS로 풀 수 있고, DFS로 풀 수 있는건 BFS로도 풀 수 있는 경우가 대부분이다.

DFS로 풀 수 있는건 BFS로도 풀 수 있다. 둘 다 완탐이기 때문이다.

2차원 맵 또한 Graph처럼 볼 수 있다.

BFS,DFS에 대해서 간단히 알아보았다. 문제에서는 2차원 배열을 많이 주게되는데 어렵게 생각하지 말고, 이렇게 생각하면 된다. 각각 배열의 요소를 V(정점)으로, 각각의 배열과 인접하는 곳을 연결하는걸 간선으로 생각하면 2차원 맵을 왜 graph처럼 볼 수 있는지 알게된다. 그림으로 표현하자면, 오른쪽 배열에 인접해 있는걸 왼쪽과 같이 그래프의 관계로 나타낼 수 있게 된다. (물론, 그림에서는 3개이지만, 4개라고 생각해주면 감사합니당.)

2차원 맵 BFS로 탐색 - 코드로 작성하기

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define X first
#define Y second
using namespace std;

int N,M;

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

int board[101][101];
bool visited[101][101];

bool is_outOfRange(int x,int y){
	return (x<0 || x>=N || y<0 || y>=M);
}

void bfs(int start_x,int start_y){
	queue<pair<int,int>> Q;
    Q.push({start_x,start_y});
    visited[start_x][start_y] = true;
    while(!Q.empty()){
		pair<int,int> cur = Q.front();
        Q.pop();
        for(int dir=0;dir<4;dir++){
			int nx= cur.X+dx[dir];
            int ny= cur.Y+dy[dir];
            if(is_outOfRange(nx,ny)) continue;
            if(visited[nx][ny] || board[nx][ny] != 1) continue;
         	visited[nx][ny] = true;
            Q.push({nx,ny});
        }
	}
}

BFS는 활용방법이 다양하다.

앞으로 이야기하는 BFS의 활용방법이 있는데, 완탐으로 접근하자면 DFS로도 풀 수 있지만, 최단거리, 순차적으로 뭔가 퍼지는 요소가 있는 BFS의 특징을 이용하는 문제들은 DFS로 풀 수는 있지만 DFS의 특징을 살리지는 못한다고 생각해서 나는 BFS를 기준으로 설명을 한다. 사람마다 다르겠지만, 나는 BFS 코드가 조금 더 직관적인 것 같다.

Flood Fill

이 친구는 DFS든, BFS든 상관없다. 연결되어있는 모든 영역을 보고 싶을 때, Flood Fill을 사용하게 된다. 대표적으로 이용되는게 지뢰찾기 라던가, 연결영역 찾기 ,그림판에 채우기 기능 등이 있을 수 있다. BFS에 들어가는 Queue를 이용해서 인접한 영역 중, 연결되는 (값이 1인)곳을 찾고 , 그런 덩어리가 몇개인지, 혹은 그 중에서 제일 넓은게 얼만큼 넓은지 등을 물어보는 문제가 주로 나옵니다.

대표 문제 : BOJ 1926 그림

경로의 길이 문제

한 지점에서 다른 지점까지의 거리를 측정하는 경우에도 BFS를 이용할 수 있다. 이때는 방문배열이 아니라, 거리배열에 방문배열의 개념을 담아서 쓰면된다. 위의 BFS로직 부분에 방문배열 부분을 거리배열로 바꿔서 아래처럼 바꾸어주면 특정 지점까지의 거리를 다 기록하는 거리배열이 완성이 된다. 이때, 거리배열을 '-1'로 초기화 시켜서 시작점과 방문하지 않은 지점을 구분해주는 팁도 꼭 챙겨가자.

int dist[n][m]
void bfs(){
	....
    dist[nx][ny] = dist[cur.X][cur.Y] +1;
    ....

}