[C언어]14502. 연구소

6중 for문을 써서 벽을 세운 다음, 각각에 대해 BFS로 바이러스 퍼트림.

그리고 안전지대를 찾으면 끝!

#include <stdio.h>
#include <string.h>
 
typedef struct
{
    int x;
    int y;
}point;
 
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
int map[10][10];
int map_Copy[10][10];
int N, M, count;
point virus[10];
int MAX;
 
int CheckBound(int y, int x)
{
    if (0 > y || 0 > x || N <= y || M <= x)
        return 0;
 
    return 1;
}
 
void MapCopy()
{
    memset(map_Copy, 0, sizeof(map_Copy));
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            map_Copy[i][j] = map[i][j];
        }
    }
}
 
int Count_Zero()
{
    int c = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (map_Copy[i][j] == 0)
            {
                c++;
            }
        }
    }
    return c;
}
 
int main()
{
    count = 0;
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            scanf("%d", &map[i][j]);
 
            if (map[i][j] == 2)
            {
                virus[count].y = i;
                virus[count++].x = j;
            }
        }
    }
 
    MAX = -1;
    for (int a = 0; a < N; a++)
    {
        for (int b = 0; b < N; b++)
        {
            for (int c = 0; c < N; c++)
            {
                for (int a1 = 0; a1 < M; a1++)
                {
                    for (int b1 = 0; b1 < M; b1++)
                    {
                        for (int c1 = 0; c1 < M; c1++)
                        {
                            /////////////////////////////////////////////
                            MapCopy();
 
                            if (map_Copy[a][a1] != 0)
                                continue;
                            map_Copy[a][a1] = 1;
 
                            if (map_Copy[b][b1] != 0)
                                continue;
                            map_Copy[b][b1] = 1;
 
                            if (map_Copy[c][c1] != 0)
                                continue;
                            map_Copy[c][c1] = 1;
 
                            int visit[8][8] = { 0, };
                            for (int i = 0; i < count; i++)
                            {
                                point Q[8 * 8] = { 0, };
                                int Q_Front = -1, Q_Back = -1;
 
                                Q[++Q_Back].y = virus[i].y;
                                Q[Q_Back].x = virus[i].x;
                                visit[virus[i].y][virus[i].x] = 1;
 
                                while (Q_Front != Q_Back)
                                {
                                    int y = Q[++Q_Front].y;
                                    int x = Q[Q_Front].x;
 
                                    for (int j = 0; j < 4; j++)
                                    {
                                        int yy = y + dy[j];
                                        int xx = x + dx[j];
 
                                        if (!CheckBound(yy, xx))
                                            continue;
 
                                        if (visit[yy][xx] == 0 && map_Copy[yy][xx] == 0)
                                        {
                                            Q[++Q_Back].y = yy;
                                            Q[Q_Back].x = xx;
                                            visit[yy][xx] = 1;
                                            map_Copy[yy][xx] = 2;
                                        }
                                    }
                                }
                            }
 
                            int temp = Count_Zero();
                            if (temp > MAX)
                                MAX = temp;
                            ///////////////////////////////////////////////////////////////////////////
                        }
                    }
                }
            }
        }
    }
 
    printf("%d", MAX);
    return 0;
}