[C언어]2573. 빙산

빙하.

정답률에 비해 쉬운 문제.

BFS로 섬의 개수를 새주면서, 동시에 0이 아닌 곳 상하좌우에 0의 개수를 카운트해준다.

그리고 섬의 개수의 count가 마친 후, 섬의 개수를 판단 후 1개 이하의 섬이면, 위에서 count 해준 상하좌우 0의 개수를 빼준다.

#include <stdio.h>
#include <string.h>
 
typedef struct
{
    int x; 
    int y;
}point;
 
int R, C, Year;
int map[300][300];
int zero[300][300];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int visit[300][300] = { 0, };
int CheckBound(int y, int x)
{
    if (x < 0 || y < 0 || x >= R || y >= C)
        return 0;
 
    return 1;
}
 
int bfs()
{
    int Count_Island = 0;
    memset(zero, 0, sizeof(zero));
    memset(visit, 0, sizeof(visit));
 
    for (int i = 0; i < C; i++)
    {
        for (int j = 0; j < R; j++)
        {
            if (map[i][j] != 0 && visit[i][j] == 0)
            {
                point Q[300 * 300] = { 0, };
                int Q_Front = -1, Q_Back = -1;
 
                Q[++Q_Back].y = i;
                Q[Q_Back].x = j;
                Count_Island++;
 
                while (Q_Back != Q_Front)
                {
                    int y = Q[++Q_Front].y;
                    int x = Q[Q_Front].x;
                    int Count_Zero = 0;
 
                    for (int a = 0; a < 4; a++)
                    {
                        int yy = y + dy[a];
                        int xx = x + dx[a];
 
                        if (!CheckBound(yy, xx))
                            continue;
 
                        if (map[yy][xx] == 0)
                            Count_Zero++;
 
                        if (map[yy][xx] != 0 && visit[yy][xx] == 0)
                        {
                            Q[++Q_Back].y = yy;
                            Q[Q_Back].x = xx;
                            visit[yy][xx] = 1;
                        }
                    }
                    zero[y][x] = Count_Zero;
                }
            }
        }
    }
 
    return Count_Island;
}
 
 
 
int main()
{
    scanf("%d %d", &C, &R);
 
    for (int i = 0; i < C; i++)
    {
        for (int j = 0; j < R; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
 
    while (1)
    {
 
        int Island = bfs();
 
        if (Island >= 2)
        {
            printf("%d\n", Year);
            return 0;
        }
        else if(Island<=0)
        {
            printf("0\n");
            return 0;
        }
 
        for (int i = 0; i < C; i++)
        {
            for (int j = 0; j < R; j++)
            {
                map[i][j] = map[i][j] - zero[i][j];
                if (map[i][j] < 0)
                    map[i][j] = 0;
            }
        }
 
        Year++;
    }
 
    return 0;
}