BOJ 2573:: 빙산

2018년 1월 19일

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

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

  1. 1년 후 빙산의 상태를 계산하는 함수
  2. 빙산의 개수를 세는 함수: 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;
}
PS