BOJ 2573:: 빙산

http://acmicpc.net/problem/2573

굉장히 비슷한 문제가 많습니다. 안전 영역(2468번) 등등. 다들 Naive하게 풀리는 문제들입니다.

두 가지 함수를 구현해야 합니다.

  • 1년 후 빙산의 상태를 계산하는 함수 (melt)
  • 빙산의 개수를 세는 함수 (num_iceberg) – DFS/BFS 사용

이걸 써서 빙산 개수가 하나가 아니게 될 때까지 매년마다 빙산 개수를 세면 됩니다. 만약 빙산 개수가 0이 되면 다 녹을 때까지 분리가 안 되는 거니까 0을 출력하고, 2개 이상이 되면 그 때 연도를 출력합니다.

#include<cstdio>
 
 
using namespace std;
 
int n, m;
int Height[300][300];
bool IsIce[300][300];
 
int Adj[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
 
 
void dfs(int i, int j) {
    if (IsIce[i][j]) {
        IsIce[i][j] = false;
        for (int k = 0; k < 4; k++)
            dfs(i + Adj[k][0], j + Adj[k][1]);
    }
}
 
 
int num_iceberg(void) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            IsIce[i][j] = Height[i][j] > 0? true : false;
 
    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (IsIce[i][j]) {
                cnt++;
                dfs(i, j);
            }
 
    return cnt;
}
 
 
void melt(void) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (Height[i][j] > 0)
                for (int k = 0; k < 4; k++)
                    if (Height[i][j] > 0 && Height[i + Adj[k][0]][j + Adj[k][1]] == -1)
                        Height[i][j]--;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (Height[i][j] == 0)
                Height[i][j] = -1;
}
 
 
int main(void) {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            scanf("%d", &Height[i][j]);
            if (Height[i][j] == 0)
                Height[i][j] = -1;
        }
 
    int y = 0, ni;
    while ((ni = num_iceberg()) == 1) {
        melt();
        y++;
    }
    printf("%d", ni > 1? y : 0);
    
    return 0;
}