[백준 1926/c++] 그림

BFS 의 대표 기본 문제

칠해졌는지 아닌지를 판단하기 위해 2차원 보드에 값을 넣어 확인하고

이전에 방문 여부를 위해 보드 크기만큼의 visited 배열을 만들어 확인,

이동 가능 하다면 그 좌표를 큐에 넣고, 방문제크 한 후

큐에서 좌표를 하나씩 빼가며, 뺀 것을 체크할 현재 좌표라 하고, 현재 좌표에 이동가능한 상하좌우 범위를

2개의 배열을 사용해서 이동 후의 4개의 좌표 값을 구현, 이동 후의 좌표 값이

범위 밖이거나, 칠해지지 않았는지의 예외 조건이 아니라면 그 예상 좌표를 방문처리하고 큐에 넣어

계속 진행해나간다

그림의 수는 전체 2차원 보드를 이중 for문으로 하나씩 돌며, 칠해졌는데 방문하지 않은 것들을 위의 과정으로

체크해나가면서 파악하면 된다. 칠해진 영역의 수는 BFS 중에 큐에 들어가는 수를 세기만 하면 된다

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

1926번: 그림

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

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

int main(){
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int paints_num = 0;
	int max_area = 0;
	
	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 (board[i][j] == 0 || visited[i][j])
			{
				continue;
			}
			paints_num++;
			queue<pair<int, int>> Q;
			visited[i][j] = 1;
			Q.push({i, j});
			int area = 0;
			while (!Q.empty())
			{
				area++;
				pair<int, int> current;
				current = Q.front();
				Q.pop();
				for (int direction = 0; direction < 4; direction++)
				{
					int nx = current.first + dx[direction];
					int ny = current.second + dy[direction];
					if (nx < 0 || nx >= n || ny < 0 || ny >= m)
					{
						continue;
					}
					if (visited[nx][ny] || board[nx][ny] != 1)
					{
						continue;
					}
					visited[nx][ny] = 1;
					Q.push({nx, ny});
				}
			}
			max_area = max(max_area, area);
		}
	}
	cout << paints_num << '\n' << max_area;
	
	return 0;
}