[BOJ] 1926. 그림 - C++

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

 

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int board[502][502];
bool vis[502][502];

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 amount = 0;
	int mx = 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] = 1;
			Q.push({ i,j });
			amount++;
			int area = 0;
			while (!Q.empty()) {
				pair<int, int> cur = Q.front(); Q.pop();
				area++;
				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 (vis[nx][ny] || board[nx][ny] != 1) continue;
					vis[nx][ny] = 1;
					Q.push({ nx,ny });
				}
				if (area > mx) mx = area;

			}
		}
	}

	cout << amount << '\n' << mx;
}

 

1. i,j를 탐색해서 board가 1이면서 방문하지 않았던 곳을 탐색하여 큐에 넣는다.

2. 이 시점부터 계산하면 그림의 개수를 셀 수 있다.

3. 큐가 빌때까지 bfs 실행 

4. area(넓이)가 mx보다 크면 mx에 현재 area크기 할당