[백준 c++] 14502 연구소

문제 설명

https://www.acmicpc.net/problem/14502
N×M 크기의 배열이 0은 빈 칸, 1은 벽, 2는 바이러스로 구성된다.
바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.
새로 벽을 3개 세운 뒤, 바이러스가 퍼졌을 때 안전 영역(0)의 최대 개수를 구하는 문제다.

아이디어

N x M의 범위가 (3 ≤ N, M ≤ 8)이라서 벽을 세우기 위해 3중 for문을 이용하더라도 시간초과가 나지 않는다.

1. new 벽 세우기
2. 바이러스 퍼뜨리기(DFS)
3. 안전영역 개수 세기

어떻게 풀어야할지는 바로 알았는데 🚨벽을 3개 선택하는 거랑 새로 세울 벽을 선택한 뒤, 🚨초기화해주는 작업을 하는 것을 제대로 못해서 푸는 데 오래걸렸다..

전체 코드

#include <iostream>
#include <vector>
using namespace std;
int n, m;
int a[8][8];
int cpy[8][8];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int y1, x1, y2, x2, y3, x3;
vector<int> res;

void dfs(int mp[8][8], int y, int x)
{
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (ny < 0 || nx < 0 || ny >= n || nx >= m)
            continue;
        if (mp[ny][nx] == 0)
        {
            mp[ny][nx] = 2;
            dfs(mp, ny, nx);
        }
    }
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
        }
    } // origin 2차원 배열 입력받기

    // 3개 좌표 고르기
    for (int i = 0; i < n; i++)
    {
        for (int u = 0; u < n; u++)
        {
            for (int f = 0; f < m; f++)
            {
                cpy[u][f] = a[u][f];
            }
        } // copy하는 2차원 배열 생성

        for (int j = 0; j < m; j++)
        {
            if (cpy[i][j] == 0)
            {
                y1 = i;
                x1 = j;
                cpy[i][j] = 1; //새로운 벽으로 고름(1번째 좌표)

                for (int k = i; k < n; k++)
                {
                    for (int l = 0; l < m; l++)
                    {
                        if (cpy[k][l] == 0)
                        {
                            if (k == i && l < j)
                                continue;

                            y2 = k;
                            x2 = l;
                            cpy[k][l] = 1; //새로운 벽으로 고름(2번째 좌표)

                            for (int p = k; p < n; p++)
                            {
                                for (int q = 0; q < m; q++)
                                {
                                    if (cpy[p][q] == 0)
                                    {
                                        if (p == k && q < l)
                                            continue;
                                        y3 = p;
                                        x3 = q;
                                        cpy[p][q] = 1;

                                        // dfs함수 실행
                                        for (int b = 0; b < n; b++)
                                        {
                                            for (int c = 0; c < m; c++)
                                            {
                                                if (cpy[b][c] == 2)
                                                    dfs(cpy, b, c);
                                            }
                                        }

                                        int cnt = 0;

                                        for (int e = 0; e < n; e++)
                                        {
                                            for (int r = 0; r < m; r++)
                                            {
                                                if (cpy[e][r] == 0)
                                                    cnt++;
                                            }
                                        }
                                        res.push_back(cnt);
                                        for (int u = 0; u < n; u++)
                                        {
                                            for (int f = 0; f < m; f++)
                                            {
                                                cpy[u][f] = a[u][f];
                                            }
                                        }
                                        cpy[y1][x1] = 1;
                                        cpy[y2][x2] = 1;
                                    }
                                }
                                if (p == n - 1)
                                {
                                    for (int u = 0; u < n; u++)
                                    {
                                        for (int f = 0; f < m; f++)
                                        {
                                            cpy[u][f] = a[u][f];
                                        }
                                    }
                                    cpy[y1][x1] = 1;
                                }
                            }
                        }
                    }
                    if (k == n - 1)
                    {
                        for (int u = 0; u < n; u++)
                        {
                            for (int f = 0; f < m; f++)
                            {
                                cpy[u][f] = a[u][f];
                            }
                        }
                    }
                }
            }
        }
        if (i == n - 1)
        {
            cpy[y1][x1] = 0;
        }
    }
    sort(res.begin(), res.end());
    reverse(res.begin(), res.end());

    cout << res[0] << "\n";
}