16946번: 벽 부수고 이동하기 4
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다. 각각의 벽에 대해서 다음을 구해보려고 한다. 벽을 부수고 이동할 수 있는 곳으로 변경한다. 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.
www.acmicpc.net
맵의 크기가 10^6이고, 최악 매번 10^6만큼 탐색을 수행하면 10^12이고, 10^9를 초과한다.
벽을 시작점으로 빈칸을 탐색하면 중복 연산이 발생한다.
이를 방지하기 위해서는 빈칸을 시작점으로 빈칸을 탐색하여 빈칸 그룹들의 크기를 산출한다. -> 10^6
벽마다 인접한 빈칸 그룹 크기를 합산 -> 10^6
map을 출력 -> 10^6
#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;
int R, C;
string str;
int map[1000][1000];
int blk[1000001][2], blkn = 1, blks[1000001];
int blkg[1000][1000];
unordered_set<int> vstg;
int wall[1000000][2], walln;
int vst[1000][1000], vstn;
int sz;
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
void dfs(int g, int r, int c) {
blkg[r][c] = g;
++sz;
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || R <= nr || nc < 0 || C <= nc || blkg[nr][nc] == g || map[nr][nc]) {
continue;
}
dfs(g, nr, nc);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> R >> C;
for (int r = 0; r < R; ++r) {
cin >> str;
for (int c = 0; c < C; ++c) {
map[r][c] = str[c] - '0';
if (map[r][c]) {
wall[walln][0] = r;
wall[walln][1] = c;
walln++;
}
else {
blk[blkn][0] = r;
blk[blkn][1] = c;
blkn++;
}
}
}
--blkn;
for (int i = 1; i <= blkn; ++i) {
if (!blkg[blk[i][0]][blk[i][1]]) {
sz = 0;
dfs(i, blk[i][0], blk[i][1]);
blks[i] = sz;
}
}
for (int i = 0; i < walln; ++i) {
int r = wall[i][0], c = wall[i][1];
vstg.clear();
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || R <= nr || nc < 0 || C <= nc) {
continue;
}
vstg.emplace(blkg[nr][nc]);
}
for(auto g : vstg){
map[r][c] += blks[g];
}
}
for (int r = 0; r < R; ++r) {
for (int c = 0; c < C; ++c) {
cout << map[r][c] % 10;
}
cout << '\n';
}
return 0;
}