1. 각 맵의 빈공간마다 각자의 크기를 BFS로 구함
2. 이때, 각자의 id를 지정하여 같은 집합에 속하면 같은 id를 갖도록 하자
3. BFS가 끝나면 각 벽을 검사
-> 주변에 인접한 모든 빈공간의 아까 구한 크기를 모두 더하고 자기자신 + 1해서 리턴
-> 이때, 주변에 인접한 빈공간들의 id 중 겹치는 것이 있는지 확인하면서 넣자. id가 같은 것이 이미 들어가있으면 그것은 더하지 않는다.
주의점
1. memset으로 visit을 매 BFS마다 초기화시켰는데, 최대 10만번 BFS를 실시하니, 10만 x 10만 회의 연산이 진행된다.
-> 따라서 BFS로 넣어진 것들만 false로 초기화 시키자
코드
#include <iostream>#include <string>#include <vector>#include <list>#include <cstring>#define MAX_N 1000#define MAX_M 1000using namespace std;typedef struct Location { int row; int col;} Location;int n, m, BFSMap[MAX_N][MAX_M][2], result[MAX_N][MAX_M];Location q[MAX_N * MAX_M];bool map[MAX_N][MAX_M], visit[MAX_N][MAX_M];void generateBFS();void generateResult();void BFS(int row, int col, int id);int getResult(int row, int col);int main() { cin >> n >> m; for (int i = 0; i < n; i++) { string s; cin >> s; for (int j = 0; j < m; j++) { map[i][j] = s[j] - '0'; } } generateBFS(); generateResult(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) cout << result[i][j]; cout << "\n"; }}void generateBFS() { int id = 1; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (map[i][j] == 0 && BFSMap[i][j][0] == 0) BFS(i, j, id++);}void BFS(int row, int col, int id) { int index = 0, first = 0; q[index++] = { row, col }; visit[row][col] = true; while (first < index) { Location temp = q[first++]; if (temp.row > 0 && map[temp.row - 1][temp.col] == 0 && !visit[temp.row - 1][temp.col]) { q[index++] = { temp.row - 1, temp.col }; visit[temp.row - 1][temp.col] = true; } if (temp.row < n - 1 && map[temp.row + 1][temp.col] == 0 && !visit[temp.row + 1][temp.col]) { q[index++] = { temp.row + 1, temp.col }; visit[temp.row + 1][temp.col] = true; } if (temp.col > 0 && map[temp.row][temp.col - 1] == 0 && !visit[temp.row][temp.col - 1]) { q[index++] = { temp.row, temp.col - 1 }; visit[temp.row][temp.col - 1] = true; } if (temp.col < m - 1 && map[temp.row][temp.col + 1] == 0 && !visit[temp.row][temp.col + 1]) { q[index++] = { temp.row, temp.col + 1 }; visit[temp.row][temp.col + 1] = true; } } for (int i = 0; i < index; i++) { BFSMap[q[i].row][q[i].col][0] = index; BFSMap[q[i].row][q[i].col][1] = id; visit[q[i].row][q[i].col] = false; }}void generateResult() { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (map[i][j] == 0) result[i][j] = 0; else result[i][j] = getResult(i, j) % 10; } }}int getResult(int row, int col) { int pickedId[4] = { -1, -1, -1, -1 }; int length = 0; int result = 0; if (row > 0) { if (BFSMap[row - 1][col][0] != 0) { result += BFSMap[row - 1][col][0]; pickedId[length++] = BFSMap[row - 1][col][1]; } } if (row < n - 1) { if (BFSMap[row + 1][col][0] != 0) { bool check = true; for (int i = 0; i < length; i++) { if (pickedId[i] == BFSMap[row + 1][col][1]) check = false; } if (check) { result += BFSMap[row + 1][col][0]; pickedId[length++] = BFSMap[row + 1][col][1]; } } } if (col > 0) { if (BFSMap[row][col-1][0] != 0) { bool check = true; for (int i = 0; i < length; i++) { if (pickedId[i] == BFSMap[row][col-1][1]) check = false; } if (check) { result += BFSMap[row][col-1][0]; pickedId[length++] = BFSMap[row][col-1][1]; } } } if (col < m - 1) { if (BFSMap[row][col+1][0] != 0) { bool check = true; for (int i = 0; i < length; i++) { if (pickedId[i] == BFSMap[row][col+1][1]) check = false; } if (check) { result += BFSMap[row][col+1][0]; } } } return result + 1;}