<백준알고리즘>16946번 BFS와 set이용 중복제거

백준16946번

접근 과정

1. 처음에는 BFS로 바탕으로 1의 위치를 입력때 큐에 담은다음에 1의 위치를 기준으로 BFS를 하는 방식으로 구현하였다.
   ->테스트 케이스는 맞았는데 시간초과가 나왔다.

2. 두 번째로 생각해 본 것은 1주변에 있는 0의 집합(그룹)안의 개수를 더하고 1을 더하면 될 것 같다는 생각
   -> 0의 그룹을 어떻게 구현할 지 생각을 못했음
   그렇게 찾아보다가 set을 이용하여 중복된 경우는 스킵하고 0의 개수를 구할 수 있는 법을 발견함.

처음에 0에서 bfs를 통해 0의 그룹들을 만들고 그룹에 따라 0이 몇개인지 저장해준다.

1을 기준으로 bfs할때 set을 이용하여 만약 x라는 그룹이 없다면 set에 x그룹을 추가해주고 0의 개수를 ans[i][j]에 더해준다. 만약 그룹이 이미 set에 존재한다면 건너뛴다. 마지막에 1본인에 해당하는 1을 ans[i][j]에 더해준다.

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <deque>



using namespace std;

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

int N, M;

int board[1001][1001] = { 0 };
int copyBoard[1001][1001] = { 0 };
int ans[1001][1001] = { 0 };

int isVisited[1001][1001] = { 0 };

queue <pair<int, int>> wallPoint;

int same_group = 0;

vector<int> zeros;

void BFS(int startY, int startX)
{
	queue<pair<int, int>> Q;
	Q.push({ startY,startX });
	int Cnt = 1;
	copyBoard[startY][startX] = same_group;
	isVisited[startY][startX] = 1;

	while (!Q.empty())
	{
		int cy = Q.front().first;
		int cx = Q.front().second;
		Q.pop();

		for (int i = 0; i < 4; i++)
		{
			int ny = cy + dy[i];
			int nx = cx + dx[i];

			if (ny > N || nx > M || ny < 1 || nx < 1 || isVisited[ny][nx] == 1 || board[ny][nx] == 1)
				continue;

			copyBoard[ny][nx] = same_group;
			isVisited[ny][nx] = 1;
			Cnt++;
			Q.push({ ny,nx });
		}
	}

	zeros.push_back(Cnt);
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;

	
	
	for (int i = 1; i <= N; i++)
	{
		string str = "";
		cin >> str;

		for (int j = 1; j <= M; j++)
		{

			board[i][j] = (str[j - 1])-'0';

			if (board[i][j] == 1)
			{
				wallPoint.push({ i,j });
			}

		}
		
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j ++)
		{
			if (isVisited[i][j] == 0 && board[i][j] == 0)
			{
				BFS(i, j);
				same_group++;
			}
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			if (board[i][j] == 1)
			{
				set<int> find_group;

				for (int k = 0; k< 4; k++)
				{
					int ny = i + dy[k];
					int nx = j + dx[k];

					if (ny > N || nx > M || ny < 1 || nx < 1 || board[ny][nx] == 1)
						continue;

					if (find_group.find(copyBoard[ny][nx]) == find_group.end())
					{
						find_group.insert(copyBoard[ny][nx]);
						ans[i][j] = ans[i][j] + zeros[copyBoard[ny][nx]];

					}
				}	

				ans[i][j]++;
				ans[i][j] %= 10;
			}
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cout << ans[i][j];
		}
		cout << '\n';
	}

	return 0;
}

<참고한 블로그>
얍문's Coding World..