무엇을 구현해야 하나
동굴에는 x로 표시된 미네랄이 있다. 막대 하나를 가로로 던져 처음 만나는 미네랄을 없애면, 일부 미네랄 덩어리가 바닥과 연결되지 않을 수 있다. 이렇게 상하좌우로 이어진 미네랄 덩어리를 클러스터라고 한다.
이 문제에서 어려운 부분은 미네랄 하나를 지우는 일이 아니다. 어느 클러스터가 공중에 떴는지 찾고, 다른 미네랄과 겹치지 않는 가장 낮은 위치까지 한 번에 옮겨야 한다.
한 번 던질 때의 처리 순서
- 입력 높이를 배열의 행 번호로 바꾼다. 입력은 바닥부터 1이지만 배열은 위부터 0이므로
row = R - height다. - 왼쪽 또는 오른쪽부터 훑어 처음 만난
x를.으로 바꾼다. - 바닥 행의 미네랄에서 BFS를 시작한다. 여기서 도달한 미네랄은 바닥에 연결되어 있으므로 떨어지지 않는다.
- 전체 동굴을 훑어 BFS로 방문하지 못한
x를 모은다. 이들이 공중에 뜬 클러스터다. - 떠 있는 칸을 잠시 지운 뒤, 각 칸 아래에서 바닥 또는 고정된 미네랄까지의 거리를 잰다. 그중 최솟값만큼 클러스터 전체를 내린다.
떠 있는 칸을 먼저 지우는 이유가 중요하다. 그대로 거리를 재면 같은 클러스터의 아래쪽 칸을 장애물로 착각할 수 있다.
낙하 거리 예시
한 클러스터의 가장 아래쪽 칸들이 바닥 또는 고정 미네랄과 각각 4칸, 2칸 떨어져 있다고 하자. 4칸을 내리면 두 번째 열에서 충돌한다. 따라서 전체 클러스터의 낙하 거리는 두 값 중 작은 2칸이다.
클러스터는 모양을 유지해야 하므로 칸마다 따로 떨어뜨리면 안 된다. 모든 칸에 같은 최솟값을 적용한다.
C++ 풀이
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Point {
int row;
int col;
};
int rows, cols;
vector<string> cave;
constexpr int DR[4] = {-1, 1, 0, 0};
constexpr int DC[4] = {0, 0, -1, 1};
bool in_range(int row, int col) {
return 0 <= row && row < rows && 0 <= col && col < cols;
}
bool break_mineral(int row, bool from_right) {
if (from_right) {
for (int col = cols - 1; col >= 0; --col) {
if (cave[row][col] == 'x') {
cave[row][col] = '.';
return true;
}
}
} else {
for (int col = 0; col < cols; ++col) {
if (cave[row][col] == 'x') {
cave[row][col] = '.';
return true;
}
}
}
return false;
}
vector<vector<bool>> find_grounded_minerals() {
vector<vector<bool>> grounded(rows, vector<bool>(cols, false));
queue<Point> q;
for (int col = 0; col < cols; ++col) {
if (cave[rows - 1][col] == 'x') {
grounded[rows - 1][col] = true;
q.push({rows - 1, col});
}
}
while (!q.empty()) {
Point current = q.front();
q.pop();
for (int direction = 0; direction < 4; ++direction) {
int next_row = current.row + DR[direction];
int next_col = current.col + DC[direction];
if (!in_range(next_row, next_col)) continue;
if (grounded[next_row][next_col]) continue;
if (cave[next_row][next_col] != 'x') continue;
grounded[next_row][next_col] = true;
q.push({next_row, next_col});
}
}
return grounded;
}
void drop_floating_cluster() {
vector<vector<bool>> grounded = find_grounded_minerals();
vector<Point> floating;
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
if (cave[row][col] == 'x' && !grounded[row][col]) {
floating.push_back({row, col});
}
}
}
if (floating.empty()) return;
for (const Point& point : floating) {
cave[point.row][point.col] = '.';
}
int drop_distance = rows;
for (const Point& point : floating) {
int next_row = point.row + 1;
while (next_row < rows && cave[next_row][point.col] == '.') {
++next_row;
}
drop_distance = min(drop_distance, next_row - point.row - 1);
}
for (const Point& point : floating) {
cave[point.row + drop_distance][point.col] = 'x';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> rows >> cols;
cave.resize(rows);
for (string& line : cave) cin >> line;
int throw_count;
cin >> throw_count;
for (int turn = 0; turn < throw_count; ++turn) {
int height;
cin >> height;
int row = rows - height;
bool from_right = (turn % 2 == 1);
if (break_mineral(row, from_right)) {
drop_floating_cluster();
}
}
for (const string& line : cave) {
cout << line << '\n';
}
}
코드에서 확인할 부분
find_grounded_minerals()는 바닥에서 출발한다. 공중 클러스터를 직접 판별하는 것보다, 확실히 고정된 미네랄을 먼저 표시하는 편이 기준이 단순하다.- 낙하할 클러스터를 지운 뒤
next_row < rows를 먼저 검사하므로 배열 밖을 읽지 않는다. - 막대가 아무 미네랄도 맞히지 않았다면 동굴 상태가 바뀌지 않으므로 BFS와 낙하 계산을 건너뛴다.
복잡도
막대를 한 번 던질 때 동굴 전체를 상수 번 훑으므로 시간 복잡도는 O(R × C)다. 막대를 N번 던지면 전체 시간은 O(N × R × C), 방문 배열과 클러스터 목록에 필요한 공간은 O(R × C)다.
미네랄 낙하 구현의 핵심은 바닥 연결 여부를 먼저 표시하고, 떠 있는 칸을 지운 상태에서 공통 낙하 거리를 구하는 것이다.
댓글