BFS란?
우리는 물고기의 색을 바꾸기 위해 그림판의 페인트 기능을 이용할 수 있다. 페인트 기능은 외부 윤곽선을 따라서 구분되는 영역의 색을 한번에 바꾸는 기능인데, Flood Fill이라고 부르기도 한다.
여기서 BFS를 통해 기능을 구현할 수 있다.
BFS는 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다. 너비를 우선으로 방문한다는 말은 무엇일까?
BFS는 원래 그래프 자료구조에서 모든 노드를 방문하기 위한 알고리즘이다. 여기서 그래프는 왼쪽과 같은 형태가 아닌, 정점과 간선으로 이루어진 오른쪽과 같은 모양의 그래프를 말한다.
예시
직접 BFS를 적용하는 예시를 살펴보자.
목표는 (0,0)과 상하좌우로 이어진 파란색 부분을 모두 확인하는 것이다.
우선 BFS를 위해서는 큐가 필요하다. 첫번째 방문한 좌표인 (0,0)을 큐에 담고, 방문한 좌표임을 체크한다. 이후에는 큐가 빌 때까지 계속해서 큐의 front원소를 빼고 해당 좌표를 기준으로 한 상하좌우 좌표를 살펴보며 큐에 넣는 작업을 반복한다.
큐의 front인 (0,0)을 pop한 뒤, 해당 원소를 기준으로 상하좌우 좌표를 살피며 파란색이면서 아직 방문하지 않은 좌표를 찾아 큐에 넣어준다.
(0,1)과 (1,0)이 큐에 담기고, 방문한 좌표로 처리한다.
같은 방법으로 (0,1)을 pop한 뒤 그 기준으로 살펴 큐에 push할 수 있는 원소를 찾는다.
이렇게 반복하며 큐가 비어있는 순간 과정은 종료되고, 서로 이어진 파란색 영역을 모두 확인 한 것을 알 수 있다.
시간복잡도는 모든 좌표가 큐에 한 번씩 들어가기때문에 N칸에서는 O(N)이 되고, MxN 매트릭스에서는 O(MN)이다.
응용 1 - 거리 측정
백준 2178 미로 탐색
풀이
입력이 붙어서 라는 점을 간과함 ,,, ㅠㅠ
getline(cin,str)로 받은 후 문자열에서 문자 - '0' 값을 매트릭스에 넣어주려고 했는데 -48이라는 엉뚱한 값이 들어감...
cin >> str 했더니 제대로 작동..
=> 원인
cin은 표준 입력 버퍼에 개행문자 \n가 남아있기 때문에, N과M을 cin으로 입력받은 후 바로 getline 함수를 사용해서 스트림을 읽고 바로 종료됨..!
getline 사용 직전,
cin.ignore() 를 추가하여 스트림 비우기 작업을 먼저 해주었더니 해결되었다.
#include <iostream>
#include <queue>
#include <utility>
#include <string>
using namespace std;
int main(void) {
int matrix[101][101];
bool visited[101][101] = {false};
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
queue <pair<int,int>> q;
int N,M,value;
string str;
pair<int,int> cur;
cin >> N >> M;
for(int i=0; i<N; i++){
cin >> str;
for(int j=0; j<M; j++){
matrix[i][j]=str[j]-'0';
}
}
visited[0][0]=true;
q.push({0,0});
while(!q.empty()){
cur = q.front();
q.pop();
for(int k=0; k<4; k++){
if(cur.first+dy[k] >=0 && cur.first+dy[k] < N && cur.second+dx[k]>=0 && cur.second+dx[k] < M){
if(matrix[cur.first+dy[k]][cur.second+dx[k]]==1 && !visited[cur.first+dy[k]][cur.second+dx[k]]){
q.push({cur.first+dy[k],cur.second+dx[k]});
visited[cur.first+dy[k]][cur.second+dx[k]]=true;
matrix[cur.first+dy[k]][cur.second+dx[k]]=matrix[cur.first][cur.second]+1;
}
}
}
}
cout << matrix[N-1][M-1];
return 0;
}시작점은 항상 matrix[0][0], 도착점은 항상 matrix[N-1][M-1]이다. 조건을 만족하여 큐에 담을 때 현재 원소 값에서 한 발 더 간다는 의미로 +1을 해주면서 matrix 배열을 걸음 수로 표현해보았다.
이렇게 한다면 visited 변수도 사용하지 않아도 됨...!
응용 2 - 시작점이 여러 개일 때
백준 7576 토마토
풀이
여기도 위와 같은 방법으로..!
대신 입력 받을 때 먼저 시작점을 찾아 큐에 넣는 작업을 하였다.
#include <iostream>
#include <queue>
#include <utility>
using namespace std;
int main(void) {
int matrix[1001][1001];
bool visited[1001][1001] = {false};
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
queue <pair<int,int>> q;
int N,M,value;
pair<int,int> cur;
int days=1;
cin >> M >> N;
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
cin >> value;
matrix[i][j]=value;
if(value==1) {
q.push({i,j});
visited[i][j]=true;
}
}
}
while(!q.empty()){
cur = q.front();
q.pop();
for(int k=0; k<4; k++){
if(cur.first+dy[k] >=0 && cur.first+dy[k] < N && cur.second+dx[k]>=0 && cur.second+dx[k] < M){
if(matrix[cur.first+dy[k]][cur.second+dx[k]]==0 && !visited[cur.first+dy[k]][cur.second+dx[k]]){
q.push({cur.first+dy[k],cur.second+dx[k]});
visited[cur.first+dy[k]][cur.second+dx[k]]=true;
matrix[cur.first+dy[k]][cur.second+dx[k]]=matrix[cur.first][cur.second]+1;
}
}
}
}
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
if(matrix[i][j] == 0) {cout << -1; return 0;}
else if(matrix[i][j] > days) days=matrix[i][j];
}
}
cout << days-1;
return 0;
}응용 3 - 시작점이 두 종류일 때
백준 4179 불!
풀이
우선 불은 반드시 네 방향으로 퍼지고, 지훈이가 갈 곳은 네 방향 중 한 방향이다. 따라서 BFS를 통해 불이 퍼질 수 있는 모든 공간에 퍼지도록 한 뒤, 불이 붙은 각 좌표에는 얼만큼의 시간이 걸렸는 지 입력한다. (위의 걸음수나 기간처럼)
그리고 다시한번 지훈이의 이동방향을 BFS를 통해 계산한다.
응용 4 - 1차원에서의 BFS
백준 1697 숨바꼭질
풀이
