#include <iostream>
#include <vector>
using namespace std;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int cheeseCount;
int n, m;
vector<vector<int>> world;
vector<vector<bool>> check;
bool boundary(int x, int y) {
if (0 <= x && x < n && 0 <= y && y < m) return true;
return false;
}
void findOx(int x, int y) {
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (boundary(nx, ny)) {
if (world[nx][ny] == 0 && check[nx][ny] == false) {
check[nx][ny] = true;
findOx(nx, ny);
}
}
}
}
void cheeseCheck() {
for (int a = 0; a < n; a++) {
for (int b = 0; b < m; b++) {
if (world[a][b] == 1) {
int oxCount = 0;
for (int i = 0; i < 4; i++) {
int nx = a + dx[i];
int ny = b + dy[i];
if (boundary(nx, ny)) {
if (check[nx][ny] == true) {
oxCount++;
}
}
}
if (oxCount >= 2) {
world[a][b] = 0;
cheeseCount--;
}
}
}
}
}
int main() {
//1. 일단 공기를 돌면서 치즈에 갖혀있는지 아닌지 판별한다
// ->가장자리 공기를 탐색하고 외부 탐색이 안 되었다면 내부 공기
//2.치즈를 녹이고 시간을 보낸후 치즈가 0개라면 시간 출력
cin >> n >> m;
world.resize(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> world[i][j];
if (world[i][j] == 1) cheeseCount++;
}
}
int phase = 0;
while (cheeseCount > 0) {
check.assign(n, vector<bool>(m, false));
//외부 공기 확인
check[0][0] = true;
findOx(0, 0);
//접촉 치즈 확인
cheeseCheck();
phase++;
}
cout << phase << '\n';
return 0;
}
//만약 가장 낮은 위치에 있는 유성과 //그 열에 가장 낮은 위치의 유성 - 가장 높은 위치에 있는 땅 //그 값들의 최소값 만큼 내려 올 수 있다.
#문제 해결 방법
전반적으로 구현 문제기 때문에 위와 같이 해결 할 수 있는데
반례를 잘 찾아야 될 것 같다.
일단 주어진 테스트케이스에서는 무조건 땅이 존재 하는것 같다.
그래서 땅이 없는 경우에는 테스트케이스가 존재 하지 않는 것 같고
땅이 있는부분과 없는 부분이 나눠진 테스트케이스가 존재하는 것 같은데
이 경우에는 땅이 있는 곳의 유성과의 차이만큼 내려주도록 구현을 해야 된다.
만약 전부 땅이 없는 경우에는 내 코드는 오류가나는데
이는 상정 안된 부분인듯하지만 딱히 명시는 안되있다.
#전체 코드
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <cmath>
#include <climits>
using namespace std;
int main() {
int r, s;
cin >> r >> s;
//만약 가장 낮은 위치에 있는 유성과
//그 열에 가장 낮은 위치의 유성 - 가장 높은 위치에 있는 땅
//그 값들의 최소값 만큼 내려 올 수 있다.
vector<vector<char>> board(r,vector<char>(s));
for (int i = 0; i < r; i++) {
string input;
cin >> input;
//board 에 입력
for (int j = 0; j < s; j++) {
board[i][j] = input[j];
}
}
int minDiff = INT_MAX;
//열을 순회하면서 가장 작은 차이를 고른다
for (int i = 0; i < s; i++) {
int maxMeteor = -1;
int maxGround = INT_MAX;
for (int j = 0; j < r; j++) {
if (board[j][i] == 'X') {
maxMeteor = j;
}
if (board[j][i] == '#' && maxGround == INT_MAX) {
maxGround = j;
}
}
// 유성이 있고, 그 아래에 땅이 있는 경우만 계산
if (maxMeteor != -1 && maxGround != INT_MAX) {
minDiff = min(maxGround - maxMeteor , minDiff);
}
}
//minDiff 만큼 유성을 아래로 내린다.
//아래부터 탐색해서 중복을 없앤다
for (int i = r - 1; i >= 0; i--) {
for (int j = 0; j < s; j++) {
if (board[i][j] == 'X') {
board[i][j] = '.';
board[i + minDiff-1][j] = 'X';
}
}
}
//복원 후 출력
for (int i = 0; i < r; i++) {
for (int j = 0; j < s; j++) {
cout << board[i][j];
}
cout << '\n';
}
return 0;
}
