#include #include #include #include using namespace std; #define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL); int bfs(vector>& V, vector>& A, int N, int M, int k, int sx, int sy) { int c = 1; queue> q; q.push({sx, sy}); V[sy][sx] = k; while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; for (int i = 0; i < 4; ++i) { int nx = x + dx[i]; int ny = y + dy[i]; if (0 <= nx && nx < M && 0 <= ny && ny < N && V[ny][nx] < k && A[ny][nx] > 0) { q.push({nx, ny}); V[ny][nx] = k; ++c; } } } return c; } int main() { fast_io(); // 빠른 입출력 활성화 int N, M; cin >> N >> M; vector> V(N, vector(M, 0)); vector> A(N, vector(M)); set> ices; vector> ttemp[2]; // 녹일 수 있는 바다를 담는 리스트 int ice = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { cin >> A[i][j]; if (A[i][j] > 0) { ++ice; ices.insert({j, i}); } else { ttemp[1].push_back({j, i}); } } } int k = 1; while (true) { int u = k % 2; bool D = false; // 얼음이 녹았는지 체크하는 변수 for (auto [x, y] : ttemp[u]) { bool P = false; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; for (int i = 0; i < 4; ++i) { int nx = x + dx[i]; int ny = y + dy[i]; if (0 <= nx && nx < M && 0 <= ny && ny < N && A[ny][nx] > 0) { P = true; // 네 방향 중 하나라도 얼음이 접해있는 바다 if (A[ny][nx] > 0) { --A[ny][nx]; if (A[ny][nx] == 0) { ttemp[1 - u].push_back({nx, ny}); ices.erase({nx, ny}); D = true; // 녹일 수 있으면 true --ice; if (ice == 0) { // 다 녹으면 처리 cout << 0 << endl; return 0; } } } } } if (P) { ttemp[1 - u].push_back({x, y}); } } ttemp[u].clear(); // 바다 리스트 갱신 if (D) { // 얼음이 1개 이상 녹았나? for (auto [i, j] : ices) { int icek = bfs(V, A, N, M, k, i, j); if (icek != ice) { // 얼음 덩어리가 나누어짐 cout << k << endl; return 0; } break; } } ++k; } return 0; }

코드 #38