백준 16932번 모양 만들기

문제

N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다.

1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 연결 요소를 모양이라고 부르자. 모양의 크기는 모양에 포함되어 있는 1의 개수이다.

배열의 칸 하나에 들어있는 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해보자.

입력

첫째 줄에 배열의 크기 N과 M이 주어진다. 둘째 줄부터 N개의 줄에는 배열에 들어있는 수가 주어진다.

출력

첫째 줄에 수 하나를 변경해서 만들 수 있는 모양의 최대 크기를 출력한다.

제한

• 2 ≤ N, M ≤ 1,000
• 0과 1의 개수는 하나 이상이다.

 

아이디어

1. 0을 1로 바꾼 뒤 다시 1을 찾아서 BFS 진행 4중 포문구조 -> 시간 초과

2. 0을 1로 바꾸고 그 좌표에서 BFS 진행 (어차피 1과 인접해 있으면 타고 갈것이므로 최대값 알수 있음)-> 시간초과 

3. 그룹을 만들어서 각 그룹별로 크기를 따로 저장. 이후 0 좌표에서 상하좌우 살펴서 크기 더해줌. 같은 그룹에 대한

중복 덧셈 방지 위해 그룹 visit 따로 만듬.

-> 그룹 visit 초기화 과정에서 100만 visit 반복 초기화로 시간초과 발생.-> idx 까지만 초기화로 변경 -> 성공

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;

int N, M;
int arr[1000][1000];
bool visit[1000][1000];
int group[1000001];
bool gvisit[1000001];


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

int main(void)
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> arr[i][j];
		}
	}

	int idx = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (arr[i][j] && !visit[i][j])
			{
				queue<pair<int, int> > que;
				que.push({ i,j });
				visit[i][j] = true;
				
				idx++;
				arr[i][j] = idx;

				int count = 1;
				while (!que.empty())
				{
					int y = que.front().first;
					int x = que.front().second;
					que.pop();

					for (int l = 0; l < 4; l++)
					{
						int newy = y + dy[l];
						int newx = x + dx[l];

						if (newy >= 0 && newy < N && newx >= 0 && newx < M)
						{
							if (arr[newy][newx] && !visit[newy][newx])
							{
								arr[newy][newx] = idx;
								visit[newy][newx] = true;
								count++;
								que.push({ newy,newx });
							}
						}
					}
				}
				group[idx] = count;
				
			}
		}
	}


	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (!arr[i][j])
			{
				int res = 1;
				memset(gvisit, 0, sizeof(gvisit));
				for (int l = 0; l < 4; l++)
				{
					int newy = i + dy[l];
					int newx = j + dx[l];

					if (newy >= 0 && newy < N && newx >= 0 && newx < M)
					{
						if (!gvisit[arr[newy][newx]])
						{
							res += group[arr[newy][newx]];
							gvisit[arr[newy][newx]] = true;
						}
					}
				}
				if (res > maxa)
				{
					maxa = res;
				}
			}
		}
	}

	cout << maxa << endl;
}