BFS(1)

올 것이 왔습니다...

https://www.youtube.com/watch?v=ftOmGdm95XI&t=653s

 

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

좌표를 담을 큐가 필요
1. 시작하는 칸을 큐에 넣고 방문 표시를 남김
2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3을 진행
3. 해당 칸을 이전에 방분했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
4. 큐가 빌때까지 2를 반복

모든 칸이 큐에 한 번씩 들어가므로 시간복잡도는 N개의 칸에 대해 O(N)

---

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

1926번: 그림

가장 기본적인 BFS 문제였습니다.

#include<bits/stdc++.h>
using namespace std;
int board[501][501];
bool vis[501][501];
int n,m;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>board[i][j];
		}
	}
	int mx=0;//최대 넓이 
	int num=0;//그림 수 
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(board[i][j]==0 || vis[i][j]) continue;
			int a=0;
			num++; 
			queue<pair<int,int>> Q;
			Q.push({i,j});
			vis[i][j]=true;
			while(!Q.empty()){
				a++;
				pair<int,int> cur=Q.front(); Q.pop();
				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(board[nx][ny]==0 || vis[nx][ny]) continue;
					Q.push({nx,ny});
					vis[nx][ny]=true;
				}
			}
			mx=max(mx,a);
		}
	}
	cout<<num<<'\n'<<mx;
	return 0;
}

---

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

1012번: 유기농 배추

문제 이름만 바뀌었지 그림과 같은 문제이다.

#include<bits/stdc++.h>
using namespace std;
int board[52][52];
bool vis[52][52];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int t,m,n,k;

int main(){
	ios::sync_with_stdio(0);
  	cin.tie(0);
	cin>>t;
	while(t--){
		cin>>m>>n>>k;
		for(int i=0;i<k;i++){
			int x,y;
			cin>>x>>y;
			board[y][x]=1;
		}
		int worm=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(board[i][j]!=1||vis[i][j]) continue;
				queue<pair<int,int>> Q;
				vis[i][j]=true;
				Q.push({i,j});
				while(!Q.empty()){
					auto cur=Q.front(); Q.pop();
					for(int dir=0; dir<4; dir++){
						int nx=cur.first+dx[dir];
						int ny=cur.second+dy[dir];
						if(nx<0||ny<0||nx>=n||ny>=m) continue;
						if(board[nx][ny]!=1||vis[nx][ny]) continue;
						Q.push({nx,ny});
						vis[nx][ny]=true;
 					}
				}
				worm++;
			}
		}
		cout<<worm<<'\n';
		for(int i=0;i<n;i++){
			fill(board[i],board[i]+m,0);
			fill(vis[i],vis[i]+m,false);
		}
	}
	return 0;
}

---

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

2468번: 안전 영역

처음에 문제 이해를 못해서 손을 대지 못했었는데, 이해하니 쉬운 문제였다. 

#include<bits/stdc++.h>
using namespace std;
int n,mxlim,mxcnt;
bool vis[103][103];
int board[103][103];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main(){
	ios::sync_with_stdio(0);
  	cin.tie(0);
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>board[i][j];
			mxlim=max(mxlim,board[i][j]);
		}
	}
	for(int limit=0;limit<=mxlim;limit++){
		for(int i=0;i<n;i++) fill(vis[i],vis[i]+n,0);
		
		int cnt=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(vis[i][j]||board[i][j]<=limit) continue;
				queue<pair<int,int>> Q;
				Q.push({i,j}); vis[i][j]=true;
				while(!Q.empty()){
					auto cur=Q.front();Q.pop();
					for(int dir=0;dir<4;dir++){
						int ny=cur.first+dy[dir];
						int nx=cur.second+dx[dir];
						if(ny<0||nx<0||ny>=n||nx>=n) continue;
						if(vis[ny][nx]||board[ny][nx]<=limit) continue;
						Q.push({ny,nx}); vis[ny][nx]=true;
					}
				}
				cnt++;
			}
		}
		mxcnt=max(mxcnt,cnt);
	}
	cout<<mxcnt;
	return 0;
}