[백준(BOJ) 1926번] 그림 (C++)

문제 링크

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

 

문제 정보

입력

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

출력

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

 

풀이

 이중 for문을 통해 시작좌표를 구하는 방법을 알고있으면 BFS 알고리즘으로 해결할 수 있다.

 

소스 코드

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

#define X first
#define Y second

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

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int num = 0; // 그림의 개수
	int mx; // 가장 넓은 그림의 넓이
	
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (vis[i][j] || board[i][j] != 1) {
				continue; // 이미 방문했거나 색칠이 안 된 부분이면 넘어간다.
			}
			
			num++;
			
			// BFS 알고리즘 시작! (i, j)가 시작좌표
			queue<pair<int, int>> Q;
			vis[i][j] = 1;
			Q.push({i, j});
			
			int area = 0; // 넓이
			while (!Q.empty()) {
				area++;
				
				auto cur = Q.front();
				Q.pop();
				
				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});
				}
			}
			
			mx = max(mx, area);
		}
	}
	
	cout << num << '\n' << mx;
	
	return 0;
}