백준 14502번 : 연구소 C언어

https://www.acmicpc.net/problem/14502

14502번: 연구소

Code:

#include <stdio.h>
#include <string.h>
 
int n, m;
int arr[9][9] = { 0, };
int temp[9][9] = { 0, };
int temp2[9][9] = { 0, };
int visit[9][9] = { 0, };
int max = 0;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
 
void copy()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            temp[i][j] = arr[i][j];
        }
    }
}
 
void copy2()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            temp2[i][j] = temp[i][j];
        }
    }
}
 
void dfs(int a,int b)
{
    visit[a][b] == 1;
    for (int k = 0; k < 4; k++)
    {
        int x = b + dx[k];
        int y = a + dy[k];
        if (x >= 0 && x < m && y >= 0 && y < n && temp2[y][x] == 0 && visit[y][x]==0)
        {
            temp2[y][x] = 2;
            dfs(y, x);
        }
    }
}
 
void wall(int cnt)
{
    if (cnt == 3)
    {
        memset(visit, 0, sizeof(visit));
        copy2();
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (temp2[i][j] == 2 && visit[i][j]==0)
                {
                    dfs(i, j);
                }
            }
        }
        int count = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if(temp2[i][j] == 0)
                {
                    count++;
                }
            }
        }
        if (max < count)
        {
            max = count;
        }
        return;
    }
    else
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (temp[i][j] == 0)
                {
                    temp[i][j] = 1;
                    wall(cnt+1);
                    temp[i][j] = 0;
                }
            }
        }
    }
}
 
int main()
{
    scanf("%d %d", &n, &m);
    int i, j = 0;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
        {
            scanf("%d", &arr[i][j]);
        }
    }
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
        {
            if (arr[i][j] == 0)
            {
                copy();
                temp[i][j] = 1;
                wall(1);
                temp[i][j] = 0;
            }
        }
    }
    printf("%d", max);
}

이 문제는 dfs나 bfs로 풀면 풀리는 문제이다. 많은 사람들이 bfs로 푼사람이 많아서 dfs로 해결하였다. 

1. 3개의 벽의 세워야 하므로 브루트포스 방식으로 3개를 세워주었다.

2. memset으로 visit 행렬을 초기화 시키며 dfs로 바이러스의 퍼짐을 확인하였다.

3. 0의 개수를 확인하며 max값을 만들어줬다.