[C언어] 14502. 연구소(DFS)

6중 For문 대신 DFS로~

#include <stdio.h>
#include <string.h>
 
typedef struct
{
    int y;
    int x;
}point;
 
point Virus[12];
 
int map[10][10];
int V[10][10];
int C, R, Virus_num, MAX;
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
 
void Build_Wall(int y, int x, int num)
{
    V[y][x] = 1;
    if (num == 0)
    {
        int visit[10][10] = { 0, };
        int m[10][10];
 
        for (int a = 0; a < 10; a++)
            for (int b = 0; b < 10; b++)
                m[a][b] = map[a][b];
 
        for (int i = 0; i < Virus_num; i++)
        {
            int Q_Front = -1, Q_Back = -1;
            point Q[8 * 8] = { 0, };
            Q[++Q_Back].y = Virus[i].y;
            Q[Q_Back].x = Virus[i].x;
 
            while (Q_Back != Q_Front)
            {
                int y = Q[++Q_Front].y;
                int x = Q[Q_Front].x;
 
                for (int a = 0; a < 4; a++)
                {
                    int yy = y + dy[a];
                    int xx = x + dx[a];
 
                    if (m[yy][xx] == 0 && visit[yy][xx] == 0)
                    {
                        m[yy][xx] = 2;
                        visit[yy][xx] = 1;
                        Q[++Q_Back].y = yy;
                        Q[Q_Back].x = xx;
                    }
 
                }
            }
        }
 
        int zero_count = 0;
        for (int a = 1; a <= C; a++)
        {
            for (int b = 1; b <= R; b++)
            {
                if (m[a][b] == 0)
                    zero_count++;
            }
        }
        if (zero_count > MAX)
            MAX = zero_count;
 
        return;
    }
 
 
    for (int i = 1; i <= C; i++)
    {
        for (int j = 1; j <= R; j++)
        {
            if (map[i][j] == 0 && V[i][j]==0)
            {
                map[i][j] = 1;
 
                Build_Wall(i, j, num - 1);
 
                map[i][j] = 0;
            }
        }
    }
    V[y][x] = 0;
    return;
}
 
int main()
{
    memset(map, -1, sizeof(map));
    Virus_num = 0;
    MAX = -1;
    scanf("%d %d", &C, &R);
 
    for (int i = 1; i <= C; i++)
    {
        for (int j = 1; j <= R; j++)
        {
            scanf("%d",&map[i][j]);
 
            if (map[i][j] == 2)
            {
                Virus[Virus_num].y = i;
                Virus[Virus_num++].x = j;
            }
        }
    }
 
    for (int i = 1; i <= C; i++)
    {
        for (int j = 1; j <= R; j++)
        {
            if (map[i][j] == 0)
            {
                map[i][j] = 1;
 
                Build_Wall(i, j, 2);
 
                map[i][j] = 0;
            }
        }
    }
 
    printf("%d\n",MAX);
 
    return 0;
}