넓이우선탐색 BFS

넓이우선탐색, BFS

Breadth-First Search

다차원 배열이나 그래프에서 각 칸을 탐색할 때 너비를 우선으로 탐색하는 알고리즘

 

큐 사용

모든 노드 확인 O(n)

 

탐색 순서는 아래부터 반시계 방향 순서

x = 행

y = 열

 

 

7행 10열 탐색 코드

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int board[502][502] =
{ {1,1,1,0,1,0,0,0,0,0},
 {1,0,0,0,1,0,0,0,0,0},
 {1,1,1,0,1,0,0,0,0,0},
 {1,1,0,0,1,0,0,0,0,0},
 {0,1,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0} };
bool vis[502][502];
int n = 7, m = 10;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	queue<pair<int, int>> Q;

	vis[0][0] = 1;
	Q.push({ 0, 0 });

	while (!Q.empty()) {
		pair<int, int> cur = Q.front();
		Q.pop();
		cout << "(" << cur.first << ", " << cur.second << ") -> ";
		
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (vis[nx][ny] == 1 || board[nx][ny] != 1) continue;
			vis[nx][ny] = 1;
			Q.push({ nx, ny });
		}
	}

	return 0;

}

 

1. 선언 변수

board = 실제 미로

vis = 탐색 여부 저장 (c++ std 안에 visit이 있으니 쓰지 않는다.)

n, m = 행(7), 열(10)

dx, dy = 탐색 방향을 결정하는 배열

queue<pair<int, int>> Q = 탐색한 노드 pair<int, int>를 넣는 큐

 

2. 시작점

시작점에 해당하는 vis[0][0]을 탐색했다는 의미로 1로 체크하고 큐에 push()

 

3. BFS

큐에서 원소를 꺼내서 해당 칸 상하좌우 인접 칸에 대해 탐색 표시를 남기고 큐에 삽입

코드에서 for문 nx, ny는 방향으로 계산된 칸 좌표

이때, nx, ny가 바운더리 안에 있는지랑(0 < nx <= n || 0 < ny <= m)

이미 탐색했고(vis[nx][ny] == 1) 유효한 칸인지(board [nx][ny] != 1)를 반드시 확인

vis[nx][ny] = 1 로 설정하고 큐에 {nx, ny} push()

 

4. 큐가 빌 때까지 3 반복

 

구현 주의사항

1. 시작점 탐색 표시 남기기

2. 큐에서 뺄 때 탐색 표시를 남기지 않고 큐에 넣을 때 남기기

같은 칸이 큐에 여러번 들어가서 시간초과

3. 원소 바운더리 체크하기