백준 1926 그림

문제 링크 : https://www.acmicpc.net/problem/1926

의사 코드 :

for 0~n까지:
	for 0~m까지:
    	만약에 색칠이 안되어있거나 이미 방문했다면
        스킵
    그림 개수 ++;
    해당 인덱스 방문으로 설정
    큐에 push
    
    int area = 0;
    
    while(q가 비어있지 않을 때):
    	area++해서 그림의 넓이 계산하기
        큐의 프론트를 cur에 저장하기
        큐를 pop하기
        
        for문을 통해 cur의 상하좌우 확인하기
        
        	범위 체크
        	문제 없다면 상하좌우 다 방문 체크하기
        	q에 상하좌우 push하기
    그림 최대값 = 현재 최대값과 area 크기 비교한 후 큰거를 최대값으로 갱신
    
    후 최대값 출력

코드 :

#include <iostream>
#include <algorithm>
#include <queue>
#include <math.h>
#include <minmax.h>
using namespace std;

int n, m;

int arr[501][501];
bool hasVisited[501][501];

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}

	int MAX = 0; // 그림의 최댓값
	int cnt = 0; // 그림의 개수

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0 || hasVisited[i][j] == true)
				continue;
			cnt++;
			queue <pair<int, int>> q;
			hasVisited[i][j] = true;

			q.push({ i, j });

			int area = 0;

			while (q.empty() == false) {
				area++;
				pair<int, int> cur = q.front();

				q.pop();
				for (int dir = 0; dir < 4; dir++) {
					int nx = cur.first + dx[dir];
					int ny = cur.second + dy[dir];

					if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
						continue;
					}

					if (hasVisited[nx][ny] == true || arr[nx][ny] == 0) // 방문했거나 색칠이 안되어있음
						continue;
					hasVisited[nx][ny] = true;

					q.push({ nx, ny });
				}
			}
			MAX = max(MAX, area);
		}
	}
	cout << cnt << "\n" << MAX;

	return 0;
}

상하좌우로 연결된 그림의 크기와 도화지에 있는 모든 그림을 찾아내야 하는 문제였다.
이중 for문으로 각 칸이 BFS의 시작점이 될 수 있는지 체크해주면 모든 그림을 찾아낼 수 있다.