백준 16946번 벽 부수고 이동하기 4

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다.

• 벽을 부수고 이동할 수 있는 곳으로 변경한다.
• 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

출력

맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

 

1에서 BFS 돌리면 시간초과이므로 0에서 그룹지어서 그룹별 개수 세고 1의 4방면으로 각 그룹의 카운트를 더해준다.

그대신 같은 그룹의 속하는 0을 반복 더하지 않게 visit 처리 해줘야 한다.

그리고 BFS에서 4방향 탐색하면서 queue에 넣어줘야 하는데 안넣었는데 테케 맞았던 거는 4방면 안으로 모든 0이 다있었기 때문...

queue에 안넣은 것 때문에 계속 틀림.. ㅅㅂ

#include <iostream>
#include <string.h>
#include <deque>
#include<queue>
#include<vector>
#include<map>
#include <algorithm>

using namespace std;

int N, M;
char arr[1001][1001];
int check[1001][1001];
int group[1001][1001];
vector<int> gcount;

map<int, bool> visit;

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

struct Node
{
	int y;
	int x;
};

int main(void)
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> arr[i][j];
		}
	}
	memset(group, -1, sizeof(group));
	int idx = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (arr[i][j] == '0' && group[i][j] == -1)
			{
				queue<Node> que;
				que.push({ i,j });
				group[i][j] = idx;

				int count = 1;
			
				while (!que.empty())
				{
					int y = que.front().y;
					int x = que.front().x;
					que.pop();
					
					for (int k = 0; k < 4; k++)
					{
						int newy = y + dy[k];
						int newx = x + dx[k];
						if (newy >= 0 && newy < N && newx >= 0 && newx < M)
						{
							if (group[newy][newx] == -1 && arr[newy][newx] == '0')
							{
								count++;
								group[newy][newx] = idx;
								que.push({ newy,newx });
							}
						}
					}
				}
				gcount.push_back(count);
				idx++;
			}
		}
	}
	

	

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (arr[i][j] == '1')
			{
				int c = 1;
				visit.clear();
				for (int k = 0; k < 4; k++)
				{
					int newy = i + dy[k];
					int newx = j + dx[k];
					if (newy >= 0 && newy < N && newx >= 0 && newx < M)
					{
						if (group[newy][newx] != -1 && !visit[group[newy][newx]])
						{
							visit[group[newy][newx]] = true;
							c += gcount[group[newy][newx]];
						}
					}
				}
				c %= 10;
				check[i][j] = c;
			}
		}
	}
	


	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cout << check[i][j] ;
		}
		cout << endl;
	}

}