[Algorithm] BFS란?

* 해당 글은 BaaaaaaaarkingDog 님의 블로그 강의를 참고하여 작성한 글입니다.

BFS 벅업다..

BFS란?

: Breadth First Search.

- 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘

- 가까운 것부터 차례대로 탐색하는 방식

- 층 (layer) 단위로 퍼져 나간다.

---

BFS의 핵심 도구: 큐(Queue)

먼저 발견한 가까운 칸부터 처리하기 위해

FIFO(First In First Out) 인 큐를 쓴다.

---

BFS의 기본 흐름

1. 시작점을 큐에 넣는다

2. 방문 처리

3. 큐에서 하나 꺼낸다

4. 그 점과 연결된 점들을 큐에 넣는다

5. 큐가 빌 때까지 반복

---

BFS의 전형적인 코드 구조

해당 강의에서 제시해준 코드 구조이다.

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x09/BFS.cpp

basic-algo-lecture/0x09/BFS.cpp at master · encrypted-def/basic-algo-lecture

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second // paird에서 first, second를 줄여쓰기 위해
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} }; // 1이 파란 칸, 0이 빨간 칸에 대응
bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장
int n = 7, m = 10; // n = 행의 수, m = 열의 수
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 }; // 상하좌우 네 방향을 의미
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	queue<pair<int, int> > Q;
	vis[0][0] = 1; // (0,0)을 방문했다고 명시
	Q.push({ 0,0 }); // 큐에 시작점인 (0,0)을 삽입
	while (!Q.empty()) {
		pair<int, int> cur = Q.front(); Q.pop();
		cout << '(' << cur.X << ", " << cur.Y << ") -> ";
		for (int dir = 0; dir < 4; dir++) { // 상하좌우 칸을 살펴볼 것이다
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위 밖일 경우
			if (vis[nx][ny] || board[nx][ny] != 1) continue; // 이미 방문한 칸이거나 파란칸이 아닐 경우
			vis[nx][ny] = 1; // (nx, ny)를 방문했다고 명시
			Q.push({ nx, ny });
		}
	}
}

 

이해가 버거워 그림과 실행 결과를 보며 하나씩 이해해보았다.

출력 결과

가장 먼저 (0, 0)에서 탐색을 시작하여, 탐색을 한 결과이다.

dx, dy 배열을 이용한 상하좌우 탐색

코드에서 정의한 dx, dy의 순서에 따라 (1, 0)을 먼저 발견하고 Queue에 삽입.

그 후 (0,1)을 발견하고 Queue에 삽입한다.

 

다음은 먼저 Queue에 삽입된 (1, 0)의 차례이다.

(1, 0)에서도 똑같이 dx, dy를 이용하여 상하좌우를 탐색한다.

발견된 (2, 0)을 삽입한다. (0, 0)은 이미 방문하였고, (2, 1)은 빨간색이므로 삽입하지 않는다.

 

그 다음에는 (2, 0)의 차례가 아니라

Queue에서의 다음 순서인 (0, 1)이다. 주변을 탐색하니 (0, 2)를 발견했다.

이런 방식으로 파란 칸들을 쭉... 찾아간다.

---

시작점이 여러 개인 경우

현재 (0, 0)에서 시작하여 탐색은 마쳤지만, (0, 4)에서 시작하는 파란 칸들은 탐색하지 못했다. 

이를 탐색하기 위해서는 이중 for문으로 모든 칸에 시작점이 존재하는지 확인해야 한다.

 

1. 이중 for문으로 모든 칸을 순회

2. 1이고 (파란색) 아직 방문 안했으면 

3. 거기서부터 BFS 시작

 

그러면 (0,4) 에서부터 BFS 탐색을 시작하여 (3,4) 까지의 경로를 탐색할 수 있다.

 

연습 문제로는 

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

---

 

BFS는 직접 짜는 것보다 정석 틀을 외우는 방식이 더 좋다.

+ 삼성 코테엔 BFS가 자주 등장하므로 숙달 돼있어야 한다.

 

응용으로는

응용 1 - 거리 측정

응용 2 - 시작점이 여러 개일 때

응용 3 - 시작점이 두 종류일 때

응용 4 - 1차원에서의 BFS

가 있다.

 

BFS는 코딩테스트 단골 문제이기 때문에 각각 문제를 살펴보며 기록을 남겨보려고 한다.