문제 링크
https://www.acmicpc.net/problem/1926
1926번: 그림
어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.
www.acmicpc.net
섬의 개수를 파악한다고 자주 기술했었는데, 간단하게 floodfill을 수행해주면 된다.
그림의 수를 파악하고, 그림의 넓이를 담아둘 때는 방문 처리 배열을 사용한다.
#include<iostream>
#include<queue>
using namespace std;
int map[500][500], dist[500][500];
int row, col;
queue<pair<int, int> > q;
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0, };
int cnt = 0;
void bfs(pair<int, int> start) {
cnt++; //섬개수 확인
q.push(start);
dist[start.first][start.second]++;
int di = 2; //위에서 시작점 방문하면 거리 1이니까, 다음으로 들어갈 거리는 2
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nr = cur.first + dr[i];
int nc = cur.second + dc[i];
if (nr < 0 || nc < 0 || nr >= row || nc >= col || map[nr][nc] == 0 || dist[nr][nc] > 0)continue;
q.push({ nr, nc });
dist[nr][nc] = di;
di++;
}
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> row >> col;
for(int i = 0 ; i < row ; i++)
for (int j = 0; j < col; j++) {
cin >> map[i][j];
}
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++) {
if (map[i][j] == 1 && dist[i][j] == 0)
bfs({ i, j });
}
//방문처리 배열에 카운트를 해뒀기때문에 그 안에서 최댓값을 구하면 된다.
int Max = -1;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (dist[i][j] > Max)
Max = dist[i][j];
}
}
cout << cnt << '\n' << Max << '\n';
return 0;
}