백준-1926 (실버-1) BFS

 

 

해당 문제는 BFS를 사용하여 풀었습니다.

 

이중 포문을 n과 m만큼 돌려서 이미 방문했거나 그림 조각이 없다면 continue를 시키고

 

방문하지 않고 그림조각이 존재한다면 queue에 새로운 그림조각 위치를 넣었습니다.

 

BFS로 근접한 그림조각? 이 있다면 count++ 시키고 가장 큰 값을 구합니다.

전체 그림을 구하는 방법은 이중 포문에서 새로운 그림 조각이 나타날때 증감을 시켜 구할 수 있습니다.

 

 

#include <bits/stdc++.h>

using namespace std;


int board[501][501] = {0,};
int vis[501][501] = {0,};

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int n, m;

int maxs = 0;
int mins = 0;
int c = 0;

int main() {
	
	cin >> n >> m;
	
	queue<pair<int,int>> Q;
	
	for(int i = 0; i < n; i++){
		for(int j = 0;j < m; j++){
			cin >> board[i][j];
		}
	}
	

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