목차
0x00 BFS 알고리즘 설명
0x01 예시
0x02 응용1 - 거리 측정
0x03 응용2 - 시작점이 여러 개일 때
0x04 응용3 - 시작점이 두 종류일 때
0x05 응용4 - 1차원에서의 BFS
0x00 BFS 알고리즘
Breadth-First Search 너비 우선 탐색.
다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문한다.
하나의 노드를 기준으로,
깊이가 1인 모든 노드를 방문한다.
깊이가 2인 모든 노드를 방문한다.
깊이가 3인 모든 노드를 방문한다.
빠짐 없이 모든 노드를 방문하면, 탐색을 마친다. (예시 그림에서 다시 이해해보자)
특징
재귀적으로 동작하지 않는다. (반면, DFS는 재귀적으로 동작한다)
노드의 방문 여부를 반드시 검사한다. 이를 검사하지 않으면 무한 루프에 빠진다.
0x01 BFS 예시
목표: (0,0)과 상하좌우로 인접한 모든 파랑 칸을 확인하여 개수를 세자.
BFS알고리즘에서는 좌표를 담을 큐가 필요하다. 그래서 좌표 옆에 있는 작대기는 큐를 표현한 것이다.
1. (0,0)에 방문했다는 표시(검정색 점)를 남기고, 큐에 (0,0)를 넣는다.
이 초기 세팅이 끝난 후에는, 큐가 빌 때까지 계속 큐의 front()를 pop()한다.
front()에서 pop()한 좌표의 상하좌우를 살펴보면서 큐에 넣어주는 작업을 반복하게 된다.
2. 큐에서 뺀 (0,0)의 상하좌우를 확인한다.
그림에서 현재 위치한 칸은 빨강테두리고, 상하좌우 확인하고 있는 칸은 검정 테두리다.
상하좌우 중에서 (0,1) 과 (1,0)이 유효한 좌표이다.
파랑색 칸이면서 아직 방문하지 않은 칸(검정 점 표시가 없는 칸)을 큐에 넣자.
-> (0,1) 과 (1,0) 을 큐에 넣는다. 이제 큐에는 좌표가 2개 쌓였다.
3. 다음으로 넘어간다. 큐의 front()는 (0,1)이다.
(0,1)을 pop()뺀다. 참고로 (0,1)에서 (행,열)순이다.
(0,1)의 상하좌우를 확인하여 방문하지 않고, 파란칸인 것을 큐에 push한다.
(0,2)는 파란칸이면서 방문하지 않은 칸이니까 방문표시를 남기고 큐에 넣는다.
전체 과정은 여기를 참고하자.
4. 큐가 빈 순간,탐색이 종료된다. 아래는 BFS 과정을 정리한 것이다.
BFS의 시간 복잡도
방문 표시를 남기기 때문에 모든 칸은 큐에 1번씩 들어간다.
그러므로 시간 복잡도는 칸이 N개일 때 O(N)이 된다. 만약 행이 R개이고 열이 C개이면 O(RC)가 된다.
STL pair : 좌표 저장에 유용함
큐에 좌표를 넣을 때 pair로 저장하면 유용하다.
방향 배열
상하 좌우를 탐색할 때, 아래의 방향 배열 dx, dy를 정의해두고 사용하면 편리하다.
만약 3차원이 주어지고 위, 아래를 검사해야한다면, 여기에 dz를 추가하여 x,y,z를 더하고 빼면 된다.
int dx = {0, 1, 0, -1};
int dy = {1, 0, -1, 0};코드의 depth 깊게 하지 않기
유효좌표 검사 등 여러 조건 확인 시 continue를 써서 코드의 depth를 덜 깊어지게 하자. 가독성을 위함.
BFS 기본 코드
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second // pair에서 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});
}
}
}[중요] BFS 구현 시 자주 하는 실수
1. 시작점에 방문했다는 표시를 남기지 않는다.
방문 배열에 꼭 방문 표시를 남겨야 재방문 하지 않고 무한루프로 빠지지 않는다.
2. 큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문 했다는 표시를 남겼다.
같은 칸이 큐에 여러번 들어가서 시간초과나 메모리 초과가 날 수 있다.
3. 이웃한 원소가 유효범위를 벗어났는지에 대한 체크를 잘못했다.
배열 인덱스가 음수가 되거나 유효범위를 넘어가면 런타임 에러가 난다.
0x01 예시 문제 : 기본 BFS
BFS 기본 예제를 풀어본다. 백준 1926번 그림
해결 과정
1. 이중 for문으로 그림이 시작되는 칸에서 BFS를 시작한다.
2. 그림이 연결된 칸이 몇개인지 알려면? 큐에서 pop을 몇 번 하는지 센다. 그림 칸이지만, 이미 방문한 칸이라면 BFS를 시작할 수 없다.
결국 파란 칸은 큐에 딱 한번씩만 들어가니까 시간 복잡도는 칸의 갯수만큼 O(nm)이다.
0x02 응용1 - 거리 측정
미로 좌측 상단으로부터 우측 하단으로 가는 최단 경로의 길이를 찾는 문제다.
BFS를 이용해 시작점에서 연결된 다른 모든점으로의 최단 경로를 찾을 수 있다.
이번에는 방문했다는 표시 대신에, 각 칸들에 (0,0)까지의 거리를 저장한다.
미로를 저장하는 배열을 미로 -1로 초기화해두면 굳이 방문배열을 두지 않아도 방문여부를 확인할 수 있다.
// http://boj.kr/cd14bec9ecff461ab840f853ed0eb87f
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string board[102];
int dist[102][102];
int 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);
cin >> n >> m;
for(int i = 0; i < n; i++)
cin >> board[i];
for(int i = 0; i < n; i++) fill(dist[i],dist[i]+m,-1); // -1로 초기화한다
queue<pair<int,int> > Q;
Q.push({0,0});
dist[0][0] = 0;
while(!Q.empty()){
auto cur = Q.front(); Q.pop();
for(int dir = 0; dir < 4; dir++){
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 유효범위 확인
if(dist[nx][ny] >= 0 || board[nx][ny] != '1') continue; // 이미 방문했는지. 벽이 아닌지.
dist[nx][ny] = dist[cur.X][cur.Y]+1;
Q.push({nx,ny});
}
}
cout << dist[n-1][m-1]+1; // 문제의 특성상 거리+1이 정답
} // 바킹독님 코드0x03 응용2 - 시작점이 여러 개일 때
토마토가 익어가는 것이 익은 것을 중심으로 상하좌우로 퍼져간다.
토마토가 다 익기까지 필요한 최소 일 수를 구하려면?
-> 모든 익지 않은 토마토들에 대해 가장 가깝게 위치한 익은 토마토까지의 거리를 구해야한다. 익지 않은 토마토가 있다면 -1 출력.
BFS의 시작점은 '익은 토마토'다. (초록칸)
따라서 BFS의 시작점은 여러개의 익은 토마토 좌표들이다.
모든 익은 토마토의 좌표를 큐에 전부 넣는다.
그리고 BFS를 시작한다.
코드를 보며 이해해보자.
// http://boj.kr/ae38aa7eb7a44aca87e9d7928402d040
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[1002][1002];
int dist[1002][1002];
int 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);
cin >> m >> n;
queue<pair<int,int> > Q;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> board[i][j];
if(board[i][j] == 1) // 익은 토마토는 시작점이니까 큐에 넣는다.
Q.push({i,j});
if(board[i][j] == 0) // 아직 안익은 토마토는 -1 로 표시한다.
dist[i][j] = -1;
}
}
while(!Q.empty()){
auto cur = Q.front(); Q.pop();
for(int dir = 0; dir < 4; dir++){
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 유효한 범위인지?
if(dist[nx][ny] >= 0) continue; // 이미 방문.
dist[nx][ny] = dist[cur.X][cur.Y]+1;
Q.push({nx,ny});
}
}
int ans = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(dist[i][j] == -1){ // 아직 익지않은 토마토가 있으면? 실패.
cout << -1;
return 0;
}
ans = max(ans, dist[i][j]); // 가장 먼 거리.
}
}
cout << ans;
}해결 과정
1. 입력 받으면서 익은토마토만 큐에 넣는다.
2. 익지 않은 토마토는 dist 배열값을 -1로 둔다. 토마토가 없는 빈칸은 dist 배열 값이 0이다.
3. BFS를 돌면서 -1인 칸(아직 익지 않은 토마토)의 거리를 갱신해준다.
4. 마지막에서, 거리가 가장 먼 것을 찾는다.
참고) 큐에 쌓이는 거리
1. 처음 입력을 받을 때, 익은 토마토들은 거리가 0이다. (시작점은 거리가0)
2. 시작점 주변에서 익혀진 토마토는 거리가 1이 된다.
3. 1인 칸들을 pop하는 동안 거리가 2인 칸들이 push된다.
4. 거리가 2인 칸들을 검사하는 동안 거리가 3인 칸들이 push된다.
즉, 전체적인 큐의 모양을 보면 '큐에 쌓이는 순서는 반드시 거리 순'이게 된다.
이 문제는 2차원 토마토였고, 3차원 토마토 문제도 풀어보자.
0x04 응용3 - 시작점이 두 종류일 때
불과 지훈이가 동시에 움직인다. 문제를 읽어보면 막막할 수 있지만 지금 배운 BFS응용이니까 고민해보자.
지훈이가 이동하다가 미로 맨 가장자리에 도착하면 탈출시켜야 한다.
결론부터 말하면, 불의 BFS와 지훈이의 BFS를 모두 돌림으로써 해결할 수 있다.
파랑칸은 지훈이 위치고, 빨강칸은 불의 위치다.
해결 과정
1. 먼저 지훈이는 신경쓰지 말고, 불의 BFS를 돌려서 미리 각 칸에 불이 전파되는 시간을 구해둔다.
불 시간을 저장할 배열을 사용한다.
위 그림에서 '두 번째 맵'이 각 칸에 불이 전파 시간을 의미한다.
2. 그 다음에 지훈이에 대한 BFS를 돌려서 지훈이를 이동시킨다.
지훈이 이동시간을 저장할 배열을 사용한다.
이 때, 만약 지훈이가 특정 칸을 x시간에 최초로 방문할 수 있는데, 그 칸에 x시간이나 그 이전에 불이 붙는다면? 그 칸에 못가게 된다.
3. 여태 까지 BFS를 풀 때의 방문 여부 방법은?
큐 안에서 (nx, ny)를 검사할 때 방문여부를 vis[nx][ny]가 true인지 혹은 dist[nx][ny]가 0이상인지 확인했었다.
이 문제에서는 추가로 해당 칸에 불이 붙는 시간을 확인해야 한다.
// http://boj.kr/aed4ec552d844acd8853111179d5775d
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string board[1002];
int dist1[1002][1002]; // 불의 전파 시간
int dist2[1002][1002]; // 지훈이의 이동 시간
int 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);
cin >> n >> m;
for(int i = 0; i < n; i++){ // 모든 방문배열 -1로 초기화 하여 미방문 표시하기
fill(dist1[i], dist1[i]+m, -1);
fill(dist2[i], dist2[i]+m, -1);
}
for(int i = 0; i < n; i++)
cin >> board[i];
queue<pair<int,int> > Q1;
queue<pair<int,int> > Q2;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(board[i][j] == 'F'){ // 불이면 큐1에 푸시. 거리도 배열1에 0초기화.
Q1.push({i,j});
dist1[i][j] = 0;
}
if(board[i][j] == 'J'){ // 지훈이 시작점은 큐2에 푸시. 거리도 배열2에 0초기화.
Q2.push({i,j});
dist2[i][j] = 0;
}
}
}
// 불에 대한 BFS
while(!Q1.empty()){
auto cur = Q1.front(); Q1.pop();
for(int dir = 0; dir < 4; dir++){
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(dist1[nx][ny] >= 0 || board[nx][ny] == '#') continue; // 벽이거나 이미 방문했으면 지나감
dist1[nx][ny] = dist1[cur.X][cur.Y]+1;
Q1.push({nx,ny});
}
}
// 지훈이에 대한 BFS
while(!Q2.empty()){
auto cur = Q2.front(); Q2.pop();
for(int dir = 0; dir < 4; dir++){
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= m){ // 범위를 벗어났다는 것은 탈출에 성공했다는 의미. 큐에 거리 순으로 들어가므로 최초에 탈출한 시간을 출력하면 됨.
cout << dist2[cur.X][cur.Y]+1;
return 0;
}
if(dist2[nx][ny] >= 0 || board[nx][ny] == '#') continue;
if(dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.X][cur.Y]+1) continue; // 불의 전파 시간을 조건에 추가
dist2[nx][ny] = dist2[cur.X][cur.Y]+1;
Q2.push({nx,ny});
}
}
cout << "IMPOSSIBLE"; // 여기에 도달했다는 것은 탈출에 실패했음을 의미.
}0x05 응용4 - 1차원에서의 BFS
지금까지는 2차원 배열에서 상하좌우를 검사했었다.
문제에서 수빈이가 이동하는 것을 보면, 현재 위치 x를 기준으로 x+1, x-1, x*2 의 위치로 이동할 수 있다.
해결 과정
1. 시작점이 5라면, BFS의 시작점을 5로 잡고 큐에 push()한다.
2. 큐의 front()는 5다.
5에서 갈 수 있는 거리는 4, 6, 10이 되고 5에서 부터의 거리는 1이 된다.
따라서 4, 6, 10에 1을 저장한다.
3. 위치 4, 6, 10을 큐에 push() 한다.
4. 큐의 front()는 4다.
위치 4에서는 3, 5, 8에 갈 수 있다. 거리를 +1해서 거리2를 3,5,8에 저장한다.
5. 이렇게 BFS를 진행 하다가 동생이 있는 위치를 만나면 거리를 출력한다.
주의
-> 0부터 10만의 제한이 있다. 거리 이동범위가 *2가 제일크다. 아무리 멀리 가도 20만이 된다.
BFS 문제집
BFS부터는 코딩테스트에 정말 잘나오는 유형이기 때문에 문제집을 꼼꼼하게 풀고, 코드의 흐름을 익히자.
다음 시간에는 DFS를 배운다.
그림 및 공부 자료 출처 : 바킹독 알고리즘 - BFS
'알고리즘 > 실전 알고리즘' 카테고리의 다른 글
| 0x0B강 - 재귀 (0) | 2021.12.08 |
|---|---|
| 0x0A강 - DFS (0) | 2021.12.07 |
| 0x08강 - 스택의 활용(수식의 괄호 쌍) (0) | 2021.11.29 |
| 0x07강 - 덱 (0) | 2021.11.24 |
| 0x06강 - 큐 (0) | 2021.11.23 |