[백준] 그림 1926번 C++ 풀이

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

1926번: 그림

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
queue<pair<int, int>> q;
int N, M;
int arr[500][500];
bool visit[500][500];
int side[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int cnt = 0, area = 0;
void solve()
{

	for(int i=0;i<N;i++)
		for (int j = 0; j < M; j++) // 모든 정점을 방문하며 첫 방문시 그림개수(cnt) +1를 해주고 그 그림의 넓이를 구한다. 
		{
			if (arr[i][j] == 1 && visit[i][j] == false)
			{
				cnt++;
				int partArea = 1; // 첫발견 그림의 넓이 1로
				visit[i][j] = true;
				q.push(make_pair(i, j));

				while (!q.empty()) // 그림과 연결된 넓이 BFS를 통해 구한다.
				{
					int y = q.front().first;
					int x = q.front().second;
					q.pop();

					for (int k = 0; k < 4; k++)
					{
						int ny = y + side[k][0];
						int nx = x + side[k][1];
						if (nx >= 0 && ny >= 0 && ny < N && nx < M && visit[ny][nx] == false&&arr[ny][nx]==1)
						{
							visit[ny][nx] = true;
							partArea++; // 그림의 넓이 + 1 확장
							q.push(make_pair(ny, nx));
						}

					}
				}

				area = max(area, partArea); // 첫 방문의 그림을 방문하여 그 주변의 그림을 다 수색했으면, 현재 그림 넓이(area) 보다 크면 바꿔준다.
			}


		}



}

int main(void)
{
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin >> arr[i][j];

	solve();
	cout << cnt << "\n" << area;
}

 

범위나 BFS 탐색시 if문의 조건을 주의해야겠다.. 가끔 왜 안되지 하면 if문에 문제가 자주 있다...!