BFS 너비 우선 탐색

너비 우선 탐색이란?

시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘

 

방법?

1. 각 정점을 방문할 때마다 모든 인접 정점들을 검사
2. 이 때 처음 보는 정점을 방문하면 이 정점을 방문 예정이라고 기록해 둔 뒤, 별도의 위치에 저장
3. 인접한 정점을 모두 검사하고 나면, 지금까지 저장한 목록에서 다음 정점을 꺼내서 방문

즉, BFS의 방문 순서는정점의 목록에서 어떤 정점을 먼저 꺼내는지에 의해 결정

 

수행 예

 

C++ 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<int>> adj;

// 너비 우선 탐색 구현
// start에서 시작해 그래프를 너비 우선 탐색하고 각 정점의 방문 순서를 반환
vector<int> bfs(int start) {
	// 각 정점의 방문 여부
	vector<bool> discovered(adj.size(), false);
	// 방문할 정점 목록을 유지하는 큐
	queue<int> q;
	// 정점의 방문순서
	vector<int> order;

	discovered[start] = true;
	q.push(start);
	while (!q.empty()) {
		int here = q.front();
		q.pop();
		//here 방문
		order.push_back(here);
		//모든 인접 정점 검사
		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i];
			// 처음 보는 정점이면 방문 목록에 집어넣음
			if (!discovered[there]) {
				q.push(there);
				discovered[there] = true;
			}
		}
	}
	return order;
}

 

너비 우선 탐색에서는, 모든 정점은 아래와 같은 3개의 상태를 순서대로 거쳐감

1. 아직 발견되지 않은 상태

2. 발견되었지만 아직 방문되지 않은 상태 (큐에 저장)

3. 방문된 상태

 

새 정점을 발견하는 데 사용했던 간선들만을 모은 트리를 너비 우선 탐색 스패닝 트리라고 부름

 

시간 복잡도?

모든 정점을 한번씩 방문 + 정점을 방문할 때마다 인접한 모든 간선 검사

→ 인접 리스트로 구현된 경우에는 O(|V|+|E|)

→ 인접 행렬로 구현된 경우에는 O(|V|^2)

 

너비 우선 탐색과 최단 거리

너비 우선 탐색이 대개 사용되는 용도는 그래프에서의 최단 경로 문제

즉, 두 정점을 연결하는 경로 중 길이가 가장 짧은 경로를 찾는 문제

 

 

예제

백준 2178 미로탐색

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

2178번: 미로 탐색

 

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

 

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

 

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

 

풀이

→ BFS 이용

처음 위치 (0, 0)에서부터 시작해서, map의 크기를 초과하지 않는 범위 내에서 상하좌우 위치 방문하면서

map의 좌표값이 1일 경우 해당 좌표값을 (현재 위치 + 1)로 변경하고, 큐에 해당 좌표 인덱스 추가

 

코드

using namespace std;
#include <iostream>
#include <queue>

int N, M;
int map[101][101];
int dx[4] = { -1, 0, 0, 1 };
int dy[4] = { 0, -1, 1, 0 };
queue<pair<int, int>> q;

void bfs() {
	q.push(make_pair(0, 0));

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i], nx = x + dx[i];
			if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
			if (map[ny][nx] == 1) {
				map[ny][nx] = map[y][x] + 1;
				if (ny == N - 1 && nx == M - 1) cout << map[ny][nx];
				q.push(make_pair(ny, nx));
			}
		}
	}
}

int main() {
	string s;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> s;
		for (int j = 0; j < M; j++) {
			map[i][j] = s[j]-'0';
		}
	}
	bfs();

	return 0;
}

 

 

 

참고 : 알고리즘 문제해결 전략