16946번 벽 부수고 이동하기 4

이번에도 좋은 문제이다. 내가 바로 직전 문제에서 가지고 있었던 BFS에 대한 개념들을 기분좋게 지적해주었다. 나는 이전까지 BFS를 풀때 따로 check배열을 두고 풀면 거의 대부분 풀린다고 생각했었다. 그런데 이번 문제는 한층 더 들어가서 그룹화시키는 작업이 필요하다.
1. 시간 복잡도를 고려하면 일일이 해결하는 것은 말이 안된다.
2. 따라서 겹치는 작업들을 고려하여 최적화시키는 작업이 필요하다. 이번 문제에서는 그룹화작업이 필요하다.

겹치는 부분을 따로 2차원배열로 만들었는데.. 시간초과가 뜬다.
마지막 출력부분에서 상하좌우를 체크해줄때 중복을 막기위해 배열로 선언해주어서 뜬것같다.
set near이란걸 배워서 사용하였다. set함수는 중복을 제거하고 넣어준다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;
int map[1001][1001];
int ch[1001][1001];
int graph[1001][1001];
vector<int> pos;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
struct Loc {
	int x, y;
	Loc(int a, int b) {
		x = a;
		y = b;
	}
};

int main() {
	//freopen("in1.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m, save = 0;
	int cnt = 0, res=0;
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		for (int j = 1; j <= m; j++) {
			map[i][j] = s[j-1] - '0';
		}
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (map[i][j] == 0 && ch[i][j] == 0) {
				cnt = 1;
				int g = pos.size();
				queue<Loc> Q;
				Q.push(Loc(i, j));
				graph[i][j] = g;
				ch[i][j] = 1;
				while (!Q.empty()) {

					Loc tmp = Q.front();
					Q.pop();
					for (int k = 0; k < 4; k++) {
						int xx = tmp.x + dx[k];
						int yy = tmp.y + dy[k];
						if (xx > n || xx < 1 || yy<1 || yy>m) continue;
						if (map[xx][yy] == 0 && ch[xx][yy] == 0) {
							ch[xx][yy] = 1;
							Q.push(Loc(xx, yy));
							cnt++;
							graph[xx][yy] = g;
						}

					}
				}
				pos.push_back(cnt);
				//cout << "error2";
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (map[i][j] == 0) cout << "0";
			else {
				set<int> near;
				for (int k = 0; k < 4; k++) {
					int xx = i + dx[k];
					int yy = j + dy[k];
					if (xx > n || xx < 1 || yy<1 || yy>m) continue;
					if (map[xx][yy] == 0) {
						near.insert(graph[xx][yy]);
					}
				}
				int ans = 1;
				for (int g : near) {
					ans += pos[g];
				}
				cout << ans % 10;
			}
		}
		cout << '\n';
	}
	return 0;
}