0과 1로 이루어진 격자(grid)가 주어졌다고 가정해 보겠습니다. 셀의 값이 1이면 그 위치에 벽돌이 있다는 뜻입니다. 벽돌이 떨어지지 않고 유지되려면 다음 조건 중 하나를 만족해야 합니다.
- 벽돌이 격자의 최상단 행에 직접 연결되어 있는 경우
- 인접한(위, 아래, 왼쪽, 오른쪽) 벽돌 중 하나라도 떨어지지 않는 경우
이제 우리는 순차적으로 지우기(erasure) 작업을 수행합니다. 각 단계에서 위치 (i, j)를 지정하면 해당 위치의 벽돌(존재할 경우)이 사라지고, 이로 인해 연결이 끊긴 다른 벽돌들이 떨어질 수 있습니다. 우리가 구해야 할 것은 각 지우기 작업 후 떨어진 벽돌의 개수를 순서대로 담은 배열입니다.
문제 예시
예를 들어 입력이 다음과 같다고 해봅시다.
- grid = [[1,0,0,0],[1,1,1,0]]
- hits = [[1,0]]
이때 출력은 [2]가 됩니다. (1, 0) 위치의 벽돌을 제거하면 더 이상 최상단과 연결되지 않은 (1, 1)과 (1, 2) 위치의 벽돌이 함께 떨어지기 때문입니다.
해결 접근 방법
이 문제는 DFS(깊이 우선 탐색)와 역순 처리를 결합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 모든 타격을 먼저 적용한 상태에서 안정적인 벽돌을 표시해 두고, 타격을 거꾸로 되돌리면서 새로 연결되는 벽돌 묶음의 크기를 세는 것입니다.
1. 방향 배열 준비
크기 4×2의 방향 배열 dir을 정의합니다.
dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}2. dfs() 함수 정의
dfs(i, j, grid)는 (i, j)가 격자 범위 안에 있고 grid[i][j]가 1일 때만 탐색을 진행합니다.
- 범위를 벗어나거나 값이 1이 아니면 0을 반환합니다.
- ret := 1로 초기화하고, grid[i][j] := 2로 표시합니다(안정적인 벽돌임을 나타냄).
- 네 방향으로 재귀 호출하며 ret에 결과를 누적합니다.
- ret을 반환합니다.
3. notConnected() 함수 정의
notConnected(x, y, grid)는 복원된 벽돌 (x, y)가 안정 영역(값이 2인 벽돌)과 인접해 있는지 확인합니다.
- 네 방향의 좌표 (nx, ny)를 계산합니다.
- (nx, ny)가 격자 범위를 벗어나면 다음 반복으로 넘어갑니다.
- grid[nx][ny] == 2라면 true를 반환합니다.
- 모든 방향을 확인한 후 x == 0이라면 true를 반환하고, 아니면 false를 반환합니다.
4. 메인 로직(hitBricks)
- 결과 배열 ret을 선언합니다.
- 모든 타격 위치에 대해 grid[hits[i][0]][hits[i][1]] -= 1을 수행해 벽돌을 미리 제거합니다.
- 최상단 행의 모든 칸에 대해 dfs(0, i, grid)를 호출해 현재 안정적인 벽돌들을 값 2로 표시합니다.
- hits 배열을 역순으로 뒤집습니다.
- 각 타격 위치 (x, y)에 대해 grid[x][y] += 1로 벽돌을 복원한 뒤,
- grid[x][y] == 1이고 notConnected(x, y, grid)가 참이면, dfs(x, y, grid) - 1을 ret에 추가합니다(타격당한 벽돌 자신은 제외).
- 그렇지 않으면 0을 ret에 추가합니다.
- ret 배열을 다시 역순으로 뒤집아 원래 순서대로 반환합니다.
C++ 구현 코드
전체 동작을 이해하기 위해 다음 구현 예제를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
int dfs(int i, int j, vector<vector<int> >& grid){
if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] != 1) {
return 0;
}
int ret = 1;
grid[i][j] = 2;
for (int k = 0; k < 4; k++) {
ret += dfs(i + dir[k][0], j + dir[k][1], grid);
}
return ret;
}
bool notConnected(int x, int y, vector<vector<int> >& grid){
for (int k = 0; k < 4; k++) {
int nx = x + dir[k][0];
int ny = y + dir[k][1];
if (nx < 0 || ny < 0 || nx >= grid.size() || ny >= grid[0].size())
continue;
if (grid[nx][ny] == 2) {
return true;
}
}
return x == 0;
}
vector<int> hitBricks(vector<vector<int> >& grid, vector<vector<int> >& hits){
vector<int> ret;
for (int i = 0; i < hits.size(); i++) {
grid[hits[i][0]][hits[i][1]] -= 1;
}
for (int i = 0; i < grid.size(); i++) {
dfs(0, i, grid);
}
reverse(hits.begin(), hits.end());
for (int i = 0; i < hits.size(); i++) {
int x = hits[i][0];
int y = hits[i][1];
grid[x][y] += 1;
if (grid[x][y] == 1 && notConnected(x, y, grid))
ret.push_back(dfs(x, y, grid) - 1);
else
ret.push_back(0);
}
reverse(ret.begin(), ret.end());
return ret;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,0,0,0},{1,1,1,0}};
vector<vector<int>> v1 ={{1,0}};
print_vector(ob.hitBricks(v, v1));
}입력
{{1,0,0,0},{1,1,1,0}}, {{1,0}}출력
[2]
마무리
이 알고리즘의 시간 복잡도는 O(N × M + H × N × M)이며, 여기서 N×M은 격자의 크기, H는 타격 횟수입니다. 타격을 역순으로 되돌리며 DFS로 새로 연결된 벽돌 묶음만 계산하기 때문에, 매번 전체 격자를 다시 검사하는 비효율을 피할 수 있습니다. 유니온 파인드(Union-Find)를 활용하면 더욱 최적화할 수도 있습니다.