[Algorithm] DFS, BFS 정리

안녕하세요. 이번 포스팅에서는 코딩 테스트의 단골 주제라 할 수 있는 DFS, BFS를 정리해보는 시간을 갖도록 하겠습니다.

 

DFS, BFS는 그래프 탐색 알고리즘의 일종입니다. 그래프란 정점들과 그 정점들을 연결하는 간선으로 이루어진 자료구조입니다.

 

 

1. 깊이 우선 탐색, DFS (Depth First Search)

한 정점으로부터 시작하여 리프 노드(더 이상 갈 수 있는 연결된 노드가 없는 노드)까지 탐색을 한 뒤, 최초의 갈림길을 만날 때까지 역행하여 다른 길을 탐색합니다.

 

위와 같은 그래프가 있다고 해보겠습니다.

 

깊이 우선 탐색, 너비 우선 탐색은 기본적으로 탐색입니다. 즉 모든 노드를 탐색하는 것에 가장 큰 의의가 있습니다. 따라서 왼쪽부터 갈지, 오른쪽부터 갈지 즉 어떠한 노드를 시작으로 다음 노드들중 어느 노드를 먼저 탐색할지에 대한 것은 문제에 크리티컬 한 조건이 주어지지 않는 한 고려하실 필요가 없습니다.

 

저는 편의상 왼쪽부터 간다고 생각해보겠습니다.

 

1을 시작으로 왼쪽으로 계속 이동합니다. 더 이상 갈 곳이 없을 때까지 이동합니다.

 

그러면 순서대로 1, 2, 4, 6, 8을 탐색합니다.

 

노드 8에서는 더이상 갈 곳이 없으므로 한 칸 역행합니다.

 

노드 6에서 이미 8을 방문했습니다. 이미 방문한 노드는 다시 방문하지 않습니다. 따라서 노드 6에서도 더 이상 갈 곳이 없으므로 역행합니다.

 

노드 4에서 이미 6을 방문했지만 7은 방문하지 않았습니다 따라서 7을 방문합니다.

 

여기까지 그림을 그리면 다음과 같습니다.

이제 반복입니다.

 

노드 7도 더이상 갈 곳이 없으므로 4로 역행, 2로 역행, 1로 역행.

 

노드 1에서 노드 3을 방문, 

 

노드 3에서 노드 5를 방문. 이렇게 그래프의 모든 탐색이 종료됩니다.

 

방문 순서는 

1 - 2 - 4 - 6 - 8 - 7 - 3 - 5 순으로 방문을 합니다.

 

 

2. 너비 우선 탐색, BFS (Breadth First Search)

 

너비 우선 탐색은 깊이 우선 탐색과는 조금 다릅니다.

 

깊이 우선 탐색이 한 노드를 기준으로 한 방향으로 리프까지 깊이 탐색으로 이동하였다면, 너비 우선 탐색은 한 노드를 기준으로 모든 방향에 대하여 다음에 갈 수 있는 방향들을 탐색합니다.

 

 

즉 여기서 시작한다면, 

 

노드 1을 기준으로 다음번에 갈 수 있는 모든 노드들을 탐색합니다.

 

1 - 2 - 3

 

그럼 이제 노드 2, 노드 3을 각각 기준으로 다음에 갈 수 있는 노드를 탐색합니다.

즉 이런식으로 너비를 기준으로 넓혀가는 방식이 너비 우선 탐색입니다.

 

1 - 2 - 3 - 4 - 5 그리고 그다음에는 6 - 7 그리고 마지막에는 8이 탐색될 것입니다.

 

이제 예제로 한번 DFS와 BFS를 정리해보겠습니다.

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

가장 기본적인 DFS, BFS문제입니다. 모든 dfs/bfs문제는 이 문제에 나온 로직을 응용하여 해결한다고 보시면 됩니다.

한번 위 내용을 바탕으로 이 문제를 풀어보시길 바랍니다.

 

#include<bits/stdc++.h>
using namespace std; 
int n, m, startNode;
bool visited[1001];
vector<int> v[1001];
void dfs(int cur) {
	if(visited[cur]) return;
	visited[cur]=1;
	cout << cur << " ";
	for(auto next : v[cur]) dfs(next);
}
void bfs(int cur) {
	fill(visited,visited+1001,0); 
	cout << "\n";
	queue<int> q;
	q.push(cur); visited[cur]=1;
	while(!q.empty()) {
		auto cur = q.front(); q.pop();
		cout << cur << " ";
		for(auto next : v[cur]) {
			if(!visited[next]) {
				q.push(next);
				visited[next]=1;
			}	
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);	

	cin >> n >> m >> startNode;
	for(int i =0; i <m; i++) {
		int a,b; cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(int i = 0; i < 1001; i++) sort(v[i].begin(), v[i].end());
	
	dfs(startNode); 
	bfs(startNode);
 	return 0; 
}

 

3. DFS, BFS의 시간 복잡도

 

DFS와 BFS모두 O(N+E)라는 시간복잡도를 갖습니다. N은 정점의 갯수, E는 간선의 개수입니다.

 

모든 정점을 탐색하고, 모든 간선을 통해 이동하므로 O(N+E)에 비례하는 성능을 갖습니다.

 

 

4. 언제 DFS를 사용하고, 언제 BFS를 사용할까?

 

1) 기본적으로 DFS와 BFS는 그래프의 모든 정점을 탐색하는 알고리즘입니다. 따라서 별 문제의 특정한 조건이 없이 모든 점에 대해 탐색하는 것이 주된 풀이라면, 두 방법 모두 사용해도 괜찮습니다.

 

저는 개인적으로 BFS를 선호합니다. 기본적으로 DFS는 갔던 길을 역행한다는 점이 BFS보다 직관적으로 이해가 잘 안 오는 것 같습니다.

 

https://www.acmicpc.net/problem/2636

2636번: 치즈

 

 

위 문제가 대표적인 예입니다. 이 경우 둘 중 본인이 더 편하신 알고리즘을 사용하시면 됩니다.

 

<dfs 풀이>

#include <bits/stdc++.h>

using namespace std;

int n, m, res, melting_cnt;
int board[101][101];
bool visited[101][101];
const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,1,-1};
void go(int x, int y) {
	for(int i = 0; i < 4; i++) {
		int nx = x+dx[i];
		int ny = y+dy[i];
		if(!visited[nx][ny] && nx >= 0 && ny >= 0 && nx < n && ny < m) {
			visited[nx][ny]=1;
			
			if(board[nx][ny]==1) board[nx][ny]=2;
			else if(board[nx][ny]==0) go(nx,ny);
		}
	}
}
int melt() {
	int ret=0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(board[i][j]==2) ret++, board[i][j] = 0; 
		}
	}
	res++;
	return ret;
}
bool check() {
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(board[i][j]==1) return false; 
		}
	}
	return true;
}
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> n >> m;
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			int num; cin >> num;
			board[i][j] = num;
		}
	}


	while(1) {
		melting_cnt=0;
		fill(&visited[0][0], &visited[0][0] + 101*101, 0);
		visited[0][0]=1;
		go(0,0); 
		melting_cnt=melt();
		if(check()) break;
	}	
	
	cout << res << "\n" << melting_cnt << endl;
	return 0;
}

 

<bfs 풀이>

#include <bits/stdc++.h>

using namespace std;

int n, m, res, prev_res;
int board[110][110];
bool visited[101][101];
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
queue<pair<int,int>> q;

void solve() {	
	while(!q.empty()) {
		pair<int,int> cur = q.front();
		q.pop();
		for(int i = 0; i < 4; i++) {
			pair<int,int> next = {cur.first+dx[i], cur.second+dy[i]};
			if(next.first < 0 || next.second < 0 || next.first >= n || next.second >=m) continue;
			if(visited[next.first][next.second]) continue;
			visited[next.first][next.second]=1;
			if(board[next.first][next.second] == 1) board[next.first][next.second]=2; 
			if(board[next.first][next.second] == 0) q.push(next);	
		}
	}

	res+=1;
}
int melt() {
	int ret=0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(board[i][j]==2) ret++, board[i][j]=0;
		}
	}
	return ret;
}
bool check() {
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(board[i][j] == 1) return false;
		}
	}
	return true;
}
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			int num; cin >> num;
			board[i][j] = num;
		}
	}
	while(1) {
		prev_res=0;
		fill(&visited[0][0], &visited[0][0]+101*101, 0);
		visited[0][0]=1; 
		q.push({0,0});
		solve();
		prev_res=melt();
		if(check()) break;
	}
	 
	cout << res << "\n" << prev_res << endl;
	return 0;
}

 

2) 경로의 특징을 저장해야 하거나, 혹은 최장 거리를 갱신할 때 지나온 경로를 저장해야 하는 문제가 있습니다.

즉 지나온 경로에 대한 정보가 필요할 때는 DFS를 사용하시면 됩니다. BFS는 지나온 경로를 기억하는 방법이 어렵습니다.

 

3) 현재 날짜 혹은 시간 혹은 카운트를 기준으로 다음번의 카운트를 묻는 문제가 있습니다. 이경우 BFS가 유리합니다.

 

체스의 나이트를 생각해보시면 편합니다. 나이트가 n번 이동해서 갈 수 있는 모든 경우를 찾아보는 문제와 같은 경우

현재 나이트가 i번 이동한 결과를 가지고 i+1번째 이동한 결과들을 모두 구하는 방법으로 BFS가 유리합니다.

 

또한 최단거리를 구해야 하는 문제가 있습니다. 

최단거리의 경우도 BFS가 n번째 이동으로 갈 수 있는 모든 경우를 구해주기 때문에 BFS가 직관적으로 구현하기가 쉽습니다.

 

 

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.