BOJ - 1926번_그림

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하는 프로그램 작성하기

  • 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의한다.
  • 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다.
  • 그림의 넓이란 그림에 포함된 1의 개수이다.


풀이

값이 1인 지점부터 그림의 시작이므로 cnt를 세고 BFS를 시작한다. 값이 0이거나 이미 방분한 지점인 경우는 제외하고 값이 1인 지점만 큐에 넣어 다시 BFS를 시작한다. 큐가 비어있을 때까지 반복하며 area값을 증가시켜주면 연결된 그림의 넓이를 알 수 있다.


소스코드

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int vis[505][505];
int board[505][505];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			cin >> board[i][j];
		}
	}
	
	int cnt = 0, max_area = 0;
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(!board[i][j] || vis[i][j]) continue;
			cnt++;
			queue<pair<int,int>> q;
			vis[i][j] = 1;
			q.push({i,j});
			
			int area = 0;
			while(!q.empty()) {
				area++;
				pair<int,int> cur = q.front();
				q.pop();
				for(int k=0; k<4; k++) {
					int nx = cur.X + dx[k];
					int ny = cur.Y + dy[k];
					if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
					if(vis[nx][ny] || !board[nx][ny]) continue;
					vis[nx][ny] = 1;
					q.push({nx,ny});
				}
			}
			max_area = max(max_area, area);		
		}
	}
	cout << cnt << "\n" << max_area;
}