[Graph] 그래프의 탐색 - 너비 우선 탐색 (BFS, Breadth-First Search)

알고리즘, 코딩테스트/알고리즘 개념 2023. 12. 18. 01:21

다양한 그래프 탐색 알고리즘이 있지만 가장 기본이 되면서 대표적인 알고리즘은 바로 DFS와 BFS다.

특히 DFS와 BFS는 탐색 방법이 상반되는 만큼 특징과 용도가 확실히 구분되는 편이기 때문에 두 탐색 방법 모두 확실히 이해하고 자유자재로 활용할 수 있어야 한다.

나아가 문제를 만났을 때 어떤 탐색 방식을 사용하는 것이 좋을지 결정할 수 있도록 그 특징을 이해하고 다양한 유형의 문제를 접해보는 것이 좋다.

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

DFS와 함께 대표적인 그래프 탐색 알고리즘 중 하나다.
깊이 우선 탐색인 DFS와 대조적인 탐색 방법으로 한가지 경로씩 끝까지 탐색하는 DFS와 달리 각 노드의 인접한 노드들부터 탐색해가는 특징을 가진다.
따라서 시작지점에 가까운 노드들 부터 점점 멀어지는 형태로 방문한다.

그래프를 탐색해가는 방식이 마치 연결되어있는 인접한 노드들을 동시에 한 깊이 씩 방문하는 형태가 되기 때문에 자연스럽게 특정 지점에 가장 먼저 도착하는 경로가 그래프의 간선 수 기준 최단경로임을 보장한다.
하지만 간선에 가중치가 있는 경우에는 가장 적은 간선을 거친 경로가 최단경로임이 보장되지 않기 때문에 단순히 가장 먼저 도착한다고 최단경로가 되지 못하며 BFS로 최단거리를 구할 수 없게된다.
가중치 없는 그래프의 경우 BFS를, 가중치가 있는 그래프에서는 다익스트라 알고리즘(Dijkstra algorithm)를 이용해서 최단거리를 구할 수 있다.

특정 노드들 사이에 경로가 존재하는지를 확인하기 위해서도 많이 사용되는데 이 경우 DFS와 BFS를 모두 사용할 수 있다.
실제 각 그래프의 구조와 찾으려는 노드의 위치에 따라 다르겠지만 최단 경로를 통해 찾게되는 BFS가 대체로 더 빠른 탐색에 유리할 수 있다.

탐색과정

사람이 그래프를 탐색해가는 과정과 차이가 있어 탐색 과정이 직관적이지 않은 편이며 DFS보다 복잡하게 느껴질 수 있다.
특정 노드에서 인접한 노드들을 모두 순차적으로 방문하면서 탐색해간다.
마치 넓게 퍼져나가듯 가능한 모든 경로를 한칸씩 순서대로 멀어져 가며 탐색하는 방식이다.

시간 복잡도

DFS와 마찬가지로 BFS 역시 그래프의 표현 방법에 따라서 시간 복잡도가 달라진다.
그래프는 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)로 표현할 수 있는데 시간 복잡도는 각각 O(V^2), O(V+E)가 된다. (V : 정점, E : 간선)

인접행렬로 그래프를 표현하게되면 특정 한 노드에서 인접한 노드를 탐색하기 위해서 노드 수 만큼 배열을 확인해야 한다.
즉 V개의 각 노드에 대해 V번 인접행렬을 참조하기 때문에 시간복잡도는 O(V^2)이 된다.

인접 리스트로 표현하게되면 한 노드의 인접 노드를 탐색하기 위해 간선의 수 만큼만 확인하면 된다.
따라서 BFS를 최대 모든 노드의 수인 V만큼 탐색하되 각 노드에서의 탐색은 간선의 수인 E만큼 이므로 시간복잡도는 O(V+E)가 된다.

BFS의 특징

1. 방문 기록

DFS와 마찬가지로 BFS를 통해 그래프를 탐색할 때에도 방문 기록을 남기고 확인하는 과정이 중요하다.
기존에 방문한 노드를 확인 없이 재방문할 경우 탐색을 마치지 못하고 무한 루프에 빠질 수 있다.
간선에 가중치가 없는 그래프에서 BFS는 각 노드까지의 최단거리를 보장하므로 이미 방문한 적이 있는 노드는 최단 거리가 이미 확인되었다는 의미가 된다.

BFS가 많이 활용되는 2차원 Map 탐색 형식의 문제에서 방문기록은 분리된 영역을 체크하거나 수를 세는 등으로 활용되기도 한다.

2. 무한한 길이의 경로가 존재해도 탐색이 가능하다.

그래프 내에 무한한 경로가 존재하더라도 특정 노드까지의 탐색에 실패하지 않는다.
각 경로를 하나씩 끝까지 탐색해나가는 DFS의 경우 찾고자 하는 목적지로 향하는 경로보다 먼저 무한한 길이의 경로를 탐색하는 경우 목적지에 도달하지 못한다.
반면 주변에 인접한 노드, 즉 갈림길을 모두 탐색해가는 BFS의 경우 일부 무한한 길이의 경로가 존재하더라도 항상 목적지에 도달할 수 있다.

3. 가중치가 없거나 모두 같은 그래프에서 최단거리를 찾을 수 있다.

이미 여러번 언급했듯 가중치가 없는 그래프에서 특정 노드의 방문은 반드시 해당 노드의 최단거리가 된다.
인접한 모든 노드들을 동시에 찾아나가는 방식이기 때문에 항상 출발점부터 가까운 순서대로 방문한다.
정말 많은 그래프 탐색 문제에서 활용할 수 있으며 대부분의 최단거리 알고리즘의 Base라고 할 수 있다.

4. 인접한 노드들 부터 넓게 퍼져나가는 탐색 방식을 갖는다.

인접한 노드들 부터 넓게 퍼져나가는 탐색 방식이기 때문에 2차원 배열을 Map으로 활용하는 문제에서의 탐색에 많이 활용된다.
단순히 2차원 배열 형태의 Map에서 길을 찾는 것 뿐만 아니라 BOJ 7576번 토마토 문제나 BOJ 14502번 연구소 문제와 같이 주변으로 퍼지는 형태를 이용하는 문제들도 많이 있다.
BOJ 2667번 단지번호붙이기 문제나 BOJ 10026번 적록색약 문제와 같이 Map 상에서 분리된 영역을 확인하거나 수를 세는 것을 요구하는 문제에서도 활용할 수 있다.

구현 방법

BFS는 다음에 방문할 인접한 노드들을 모두 Queue에 쌓는 방식으로 구현한다.
DFS를 구현하기 위해서 후입 선출(LIFO, Last In First Out) 자료구조인 Stack을 활용하면 자연스럽게 가장 마지막에 발견한 경로부터 방문하게 되듯 선입 선출(FIFO, First In Firtst Out) 자료구조인 Queue를 이용하면 가까운 노드들부터 방문하게 된다.

Queue를 이용해 BFS를 구현하면 이렇게 인접노드들을 enqueue한 후 가장 먼저 push한 노드부터 탐색한다,

현재 방문한 노드의 인접 노드들을 모두 queue에 넣고 queue의 front부터 하나씩 꺼내 방문하고 다시 인접한 노드들을 queue에 넣는식으로 반복하면 항상 가장 먼저 방문한 노드의 인접노드들 부터 차례대로 탐색할 수 있다.

void BFS(int start) {
    queue<int> q;
    int visit[V];
    
    q.push(start);
    visit[start] = 1;
    
    while (!q.empty()) {
    	int curr = q.front();
        q.pop();
        
        for (int i = 0; i < adj[curr].size; i++) {
        	int next = adj[curr][i];
            if (visit[next] > 0) continue;
            
            q.push(next);
            visit[next] = 1;
        }
    }
}

역시 단순히 모든 노드를 탐색하는 코드는 간단하다.
중복 방문을 확인하여 끝나지 않는 무한루프에 빠지지 않도록 처리해주는 것이 중요하다.
또한 방문한 노드를 queue에서 제거해주는것을 놓친다면 마찬가지로 무한루프에 빠질 수 있으므로 주의해야 한다.

void BFS(int start, int dest) {
    queue<int> q;
    int visit[V];
    
    q.push(start);
    visit[start] = 1;
    
    while (!q.empty()) {
    	int curr = q.front();
        q.pop();
        
        if (curr == dest) break;
        
        for (int i = 0; i < adj[curr].size; i++) {
        	int next = adj[curr][i];
            if (visit[next] > 0) continue;
            
            q.push(next);
            visit[next] = 1;
        }
    }
}

경우에 따라서는 모든 노드를 queue에 넣고 queue가 빌 때까지 그래프 전체를 탐색하는것이 아니라 조건에 따라 탐색을 멈출 수도 있다.
이 때 다시 탐색이 필요하거나 여러 test case를 처리해야 한다면 queue를 BFS 함수 내에서 선언하거나 다시 탐색하기 전에 비워주는 것을 잊으면 안된다.

2차원 배열 형태의 Map을 탐색하는 문제의 예 (출처 - BAEKJOON Online Judge)

위 예시와 유사한 2차원 배열 형태의 Map을 탐색하는 유형의 문제는 기본적인 BFS를 조금만 바꾸어 탐색시킬 수 있다.
상, 하, 좌, 우 4방향 혹은 8방향의 좌표를 이용해 인접 노드를 가져오는 것 외에는 크게 다르지 않다.
이 때에는 노드 번호가 아니라 2차원 Map에서 X, Y 좌표를 queue에 넣어주면 된다.

// 2차원 배열 Map에서 1인 위치만 탐색하자

void BFS(int sratr_r, int start_c) {
	queue<pair<int, int>> q;
	int dr[] = { -1, 0, 1, 0 };
	int dc[] = { 0, 1, 0, -1 };

	q.push(make_pair(start_r, start_c));
	visit[start_r][start_c] = 1;

	while (!q.empty()) {
		int curr_r = q.front().first;
		int curr_c = q.front().second;
		q.pop();

		for (i = 0; i < 4; i++) {
			int next_r = curr_r + dr[i];
			int next_c = curr_c + dc[i];

			if (next_r < 0 || next_r >= N || next_c < 0 || next_c >= N) continue;
			if (map[next_r][next_c] == '0') continue;
			if (visit[next_r][next_c]) continue;

			visit[next_r][next_c] = 1;
			q.push(make_pair(next_r, next_c));
		}
	}
}

Map 탐색 문제에서 한번 탐색으로 도달할 수 없는 단절된 영역의 탐색이 필요한 경우 시작점을 인자로 BFS함수를 여러 차례 반복시켜 탐색을 완료할 수 있다.
여러번 탐색을 요구하고 탐색과 탐색 사이에 Map에 변화를 주는 형태의 문제에서도 유사한 방법으로 풀 수 있다.

int N;
int map[100][100];

void BFS(int sratr_r, int start_c) {
	queue<pair<int, int>> q;
	int dr[] = { -1, 0, 1, 0 };
	int dc[] = { 0, 1, 0, -1 };

	q.push(make_pair(start_r, start_c));
	visit[start_r][start_c] = 1;

	while (!q.empty()) {
		int curr_r = q.front().first;
		int curr_c = q.front().second;
		q.pop();

		for (i = 0; i < 4; i++) {
			int next_r = curr_r + dr[i];
			int next_c = curr_c + dc[i];

			if (next_r < 0 || next_r >= N || next_c < 0 || next_c >= N) continue;
			if (map[next_r][next_c] == '0') continue;
			if (visit[next_r][next_c]) continue;

			visit[next_r][next_c] = 1;
			q.push(make_pair(next_r, next_c));
		}
	}
}

int main() {
	cin.tie(0);
    cin.sync_with_stdio(0);
    
    cin >> N;
    
    for (int i = 0; i < N; i++) {
    	for (int j = 0; j < N; j++) {
        	cin >> map[i];
        }
    }
    
    for (int i = 0; i < N; i++) {
    	for(int j = 0; j < N; j++) {
        	if (map[i][j] > 0)
            	BFS(i, j);
        }
     }
    
	return 0;
}

BFS는 다익스트라(Dijkstra)와 같은 다른 최단거리 알고리즘과 구현 방식이 상당히 유사한 편이다.

따라서 최단거리 문제를 풀기 위해 BFS는 가장 기본이 되는 알고리즘이다.

2차원 배열을 Map으로 입력받아 탐색하는 방식의 문제는 특히 그래프 탐색, 최단 경로 문제에서 상당히 자주 마주치게 되는 유형이다.

저작자표시

'알고리즘, 코딩테스트 > 알고리즘 개념' 카테고리의 다른 글

[Graph] 그래프의 탐색 - 깊이 우선 탐색 (DFS, Depth-First Search) (1)	2023.12.05
[Graph] 그래프의 표현 - 인접 행렬과 인접 리스트 (Adjacency Matrix, Adjacency List) (1)	2023.09.12

ABOUT ME

JC.log JC.log

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

탐색과정

시간 복잡도

BFS의 특징

1. 방문 기록

2. 무한한 길이의 경로가 존재해도 탐색이 가능하다.

3. 가중치가 없거나 모두 같은 그래프에서 최단거리를 찾을 수 있다.

4. 인접한 노드들 부터 넓게 퍼져나가는 탐색 방식을 갖는다.

구현 방법

'알고리즘, 코딩테스트 > 알고리즘 개념' 카테고리의 다른 글

티스토리툴바

ABOUT ME

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

탐색과정

시간 복잡도

BFS의 특징

1. 방문 기록

2. 무한한 길이의 경로가 존재해도 탐색이 가능하다.

3. 가중치가 없거나 모두 같은 그래프에서 최단거리를 찾을 수 있다.

4. 인접한 노드들 부터 넓게 퍼져나가는 탐색 방식을 갖는다.

구현 방법

'알고리즘, 코딩테스트 > 알고리즘 개념' 카테고리의 다른 글

관련글 관련글 더보기

티스토리툴바