[백준BaekJoon]1926: 그림/C++

문제

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

---

코드

BFS(너비우선탐색)문제이다.

기본적인 틀은 다른 BFS 문제와 다를 것 없고, 그림의 개수와 영역을 각각 어느 부분에서 카운트 해주는지가 중요하다.

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

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m, num = 0, area, mx = 0;
	cin >> n >> m;

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

	queue<pair<int,int>> Q;//좌표값 넣는 큐

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (vis[i][j] == 0 && arr[i][j] == 1) {//방문하지 않았고 색칠이 된 구역

				vis[i][j] = 1;
				Q.push({ i,j });
				num++;
				area = 0;

				while (!Q.empty()) {//탐색 시작
					pair<int, int> cur = Q.front();
					Q.pop();
					area++;

					for (int dir = 0; dir < 4; dir++) {
						int nx = cur.first + dx[dir];
						int ny = cur.second + dy[dir];//x,y 좌표를 상하좌우로 움직여줌

						if (nx < 0 || nx > n || ny < 0 || ny > m)continue;//범위를 벗어나면 탐색 중단
						if (arr[nx][ny] != 1 || vis[nx][ny] == 1)continue;//마찬가지로 탐색하는 구역이 이미 방문했거나 색칠이 안된 경우 탐색 중단 

						vis[nx][ny] = 1;
						Q.push({ nx, ny });//새롭게 탐색할 구역 대입
					}
				}
				mx = max(mx, area);

			}

		}
	}
	cout << num << "\n" << mx;
}

	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cout << ans[i][j]<<" ";
		}
		cout << "\n";
	}
}