문제
N×M 맵에서 각 벽을 부쉈을 때 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 구하는 문제다.
벽 하나를 골라 부순 뒤 그때마다 BFS를 새로 실행하면, 벽의 수만큼 같은 빈 공간을 반복해서 탐색한다. 대신 벽을 보기 전에 빈 칸들을 연결된 덩어리로 묶고 각 덩어리 크기를 한 번만 계산한다.
벽의 상하좌우에 크기 5인 같은 덩어리가 두 번 닿더라도 10칸으로 세면 안 된다. 같은 그룹 ID는 한 번만 더해야 한다. 최종 값은 벽 자체 1칸 + 서로 다른 인접 그룹들의 크기다.
핵심 아이디어
- 모든 벽에 대해 BFS를 돌리면 시간 초과가 발생한다.
- 대신, 빈 칸들을 먼저 BFS로 그룹핑하고 각 그룹의 크기를 저장해둔다.
- 각 벽에 대해 상하좌우 인접한 서로 다른 그룹의 크기를 합산하면 된다.
set을 사용하여 같은 그룹을 중복 카운트하지 않도록 한다.
풀이
#include <iostream>
#include <queue>
#include <set>
#include <vector>
using namespace std;
int n, m;
int componentId[1000][1000];
int componentSize[1000001];
char grid[1000][1000];
vector<pair<int, int>> walls;
int dirX[4] = {1, 0, -1, 0};
int dirY[4] = {0, 1, 0, -1};
int labelComponent(int startRow, int startColumn, int id) {
queue<pair<int, int>> q;
q.push({startRow, startColumn});
componentId[startRow][startColumn] = id;
int size = 0;
while (!q.empty()) {
auto [row, column] = q.front();
q.pop();
++size;
for (int dir = 0; dir < 4; ++dir) {
int nextRow = row + dirX[dir];
int nextColumn = column + dirY[dir];
if (nextRow < 0 || nextRow >= n ||
nextColumn < 0 || nextColumn >= m) continue;
if (grid[nextRow][nextColumn] == '1') continue;
if (componentId[nextRow][nextColumn] != 0) continue;
componentId[nextRow][nextColumn] = id;
q.push({nextRow, nextColumn});
}
}
return size;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
if (grid[i][j] == '1') walls.push_back({i, j});
}
}
// 1단계: 빈 칸 그룹핑
int nextId = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '1' || componentId[i][j] != 0) continue;
componentSize[nextId] = labelComponent(i, j, nextId);
++nextId;
}
}
// 2단계: 각 벽에 대해 인접 그룹 합산
int ret[1001][1001] = {};
for (pair<int, int> w : walls) {
set<int> s;
for (int i = 0; i < 4; i++) {
int x = w.first + dirX[i];
int y = w.second + dirY[i];
if (x < 0 || x >= n || y < 0 || y >= m) continue;
int id = componentId[x][y];
if (id != 0) s.insert(id);
}
int sum = 0;
for (int t : s) {
sum += componentSize[t];
}
ret[w.first][w.second] = (sum + 1) % 10;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << ret[i][j];
}
cout << '\n';
}
return 0;
}
주요 포인트
+1은 벽 자체가 부서지면서 생기는 한 칸을 포함하기 위함이다.set으로 중복 그룹을 제거하는 것이 정확한 결과의 핵심이다.- 최대 백만 칸을 재귀 DFS로 탐색하면 호출 스택이 넘칠 수 있다. 큐를 쓰는 반복 BFS는 이 위험이 없다.
복잡도
- 시간: O(N × M)
- 공간: O(N × M)
전처리로 그룹핑해두고 벽마다 인접 그룹을 합산하는, 역발상이 필요한 BFS 문제다.
댓글