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

무지성 BFS는 시간초과가 납니다.. 괜히 골2 문제가 아니더라고용 ...

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

16946번: 벽 부수고 이동하기 4

#include <cstdio>
#include <queue>
#include <vector>
#include <set>
int R, C;
char board[1000 + 2][1000 + 2];
int ans[1000 + 2][1000 + 2];

struct _st
{
	int x, y;
};

std::queue<_st> Q;
std::vector<_st> V;
int visited[1000 + 2][1000 + 2];

struct _zt
{
	int cnt;
	int gnum;
};
_zt zeros[1000 + 2][1000 + 2];

void input()
{
	scanf("%d %d", &R, &C);
	for (int i = 0; i < R; i++) {
		scanf("%s", board[i]);
	}
}

void BFS(int x, int y)
{
	int dir_x[4] = { 0, 0 ,1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };
	Q = {};
	V.clear();

	Q.push({ x, y });
	visited[x][y] = 1;
	V.push_back({ x, y });
	

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (board[nx][ny] == '1') continue;
			if (visited[nx][ny]) continue;
			Q.push({ nx, ny });
			visited[nx][ny] = 1;
			V.push_back({ nx, ny });
		}
	}
}



void Flood_Fill()
{
	int g = 1;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (board[i][j] == '1') continue;
			if (visited[i][j]) continue;
			BFS(i, j);
			int size = V.size();
			for (_st v : V) {
				zeros[v.x][v.y] = { size, g };
			}
			g++;
		}
	}
} 

void get_zeros()
{
	int dir_x[4] = { 0, 0 ,1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };
	std::set<int> S;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (board[i][j] == '0') continue;
			S.clear();
			for (int p = 0; p < 4; p++) {
				int nx = i + dir_x[p];
				int ny = j + dir_y[p];

				if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
				if (zeros[nx][ny].cnt == 0) continue;
				auto iter = S.find(zeros[nx][ny].gnum);
				if (iter != S.end()) continue;
				ans[i][j] += zeros[nx][ny].cnt;
				S.insert(zeros[nx][ny].gnum);
			}
			ans[i][j] += 1;
			ans[i][j] %= 10;
		}
	}
}

void output()
{
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			printf("%d", ans[i][j]);
		}
		printf("\n");
	}
}




int main()
{
	input();
	Flood_Fill();	// 0의 집합을 세어준다. 
	get_zeros();
	output();
	return 0;
}

냅다 BFS 돌리면 들어가자마자 시간초과 난다.

기존에 벽 부수고 이동하기 1~3문제와는 결이 다르기 때문에 따로 포스팅함.. 

 

약간의 아이디어가 필요한 문제 같아서 시간 초과 난 후, 힌트 봤다. (질문하기 탭 매우 유용)

사람들이 다 '0의 집합을 만드세용!!'이라길래 나도 1을 기준으로 탐색하지 않고 0을 기준으로 인접한 0들의 위치를 모두 벡터에 저장했다.

BFS 함수 나와서 벡터에 저장된 좌표위치에 벡터의 사이즈(= 같은 그룹에 속한 0의 개수)를 넣어주었다. 

마지막으로 1을 기준으로 인접한 0의 개수를 구해주어야 하는데, 이때 상하좌우 탐색 시 같은 그룹이 중복으로 세어지면 안된다. 

11001
00111
01010
10101

=> (3, 1)의 1을 기준으로 상방향에 있는 0과 좌방향에 있는 0은 같은 그룹이다.

 따라서 gnum이라는 0의 그룹넘버를 같이 저장해서, set에 해당 그룹 넘버가 이미 담겨있다면 continue 하도록 처리했다.