Written by DK-Lite
on December 07, 2019

[BackJoon .1926] 그림

그림

Problem

0, 1 로 이루지어진 2차원 평면에서 가장 넓은 그림을 찾는 문제
같은 집단의 그림은 가로, 세로가 1로 연결되어 있어야한다.

주어진 2차 평면에서 그림의 갯수와 가장 넓은 그림의 넓이를 출력해야한다.

Solution

2차원 평면을 순차적으로 탐색
그림을 발견하면 주어진 규칙에 맞게 BFS탐색하고 탐색시 1을 0으로 변환
BFS 내에서는 그림의 크기를 출력하고 MAX값으로 갱신
BFS 발생시에 카운트

Code

#include <iostream>
#include <queue>
using namespace std;
int n, m;
int mat[501][501];
#define MAX(A,B) A > B ? A : B
void Insert(queue<int> &q, int x, int y) {
	if (x < 0 || x >= m || y < 0 || y >= n || mat[y][x] == 0) return;
	mat[y][x] = 0;
	q.push(x);
	q.push(y);
}
int BFS(int y, int x) {
	queue<int> q;
	q.push(x);
	q.push(y);
	mat[y][x] = 0;

	int cnt = 0;
	while (!q.empty()) {
		int x = q.front(); q.pop();
		int y = q.front(); q.pop();
		cnt++;
		Insert(q, x+1, y);
		Insert(q, x-1, y);
		Insert(q, x, y+1);
		Insert(q, x, y-1);
	}
	
	return cnt;
}
int main() {

	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> mat[i][j];

	int cntArea = 0;
	int maxArea = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (mat[i][j]) {
				int area = BFS(i, j);
				maxArea = MAX(maxArea, area);
				cntArea++;
			}

	cout << cntArea << endl << maxArea << endl;
	
}

← → Top