본인 풀이

#include <bits/stdc++.h>
using namespace std;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int a[10][10];
int copied[10][10];
int visited[10][10];
int n, m;
int cnt = 0;

int dfs(int y, int x, bool virus){
    int ret = 1;
    visited[y][x] = 1;

    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(copied[ny][nx] == 0 && visited[ny][nx] == 0){
            if(virus){
                copied[ny][nx] = 2;
            }

            ret += dfs(ny, nx, virus);
        }
    }

    return ret;
}

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

    cin >> n >> m;
    vector<pair<int, int>> v;

    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
            if(a[i][j] == 0){
                v.push_back({i, j});
            }
        }
    }

    // 빈칸인 좌표 모두를 벡터에 푸시
    vector<int> ret;
    for (int i = 0; i < v.size(); i++){
        // visited 초기화
        memset(visited, 0, sizeof(visited));
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                copied[i][j] = a[i][j];
            }
        }


        int y1, x1;
        tie(y1, x1) = v[i];

        // 빈칸이 아니면 벽을 세울수가 없음
        if(a[y1][x1] != 0){
            continue;
        }
        for (int j = i + 1; j < v.size() - 1; j++)
        {
            int y2, x2;
            tie(y2, x2) = v[j];
            if(a[y2][x2] != 0){
                continue;
            }

            for (int k = j + 1; k < v.size() - 2; k++){
                int y3, x3;
                tie(y3, x3) = v[k];
                if(a[y3][x3] != 0){
                    continue;
                }

                for (int l = 0; l < n; l++){
                    for (int p = 0; p < m; p++){
                        copied[l][p] = a[l][p];
                    }
                }

                copied[y1][x1] = 1;
                copied[y2][x2] = 1;
                copied[y3][x3] = 1;

                // 벽 세개 세우고, 2로 DFS하고
                int _ = dfs(0, 0, true);

                memset(visited, 0, sizeof(visited));


                // 마지막에 남은 구역을 0으로 DFS
                int value = 0;
                for (int aa = 0; aa < n; aa++)
                {
                    for (int bb = 0; bb < m; bb++){
                        if(copied[aa][bb] != 0 || visited[aa][bb]){
                            continue;
                        }
                        value = dfs(0, 0, false);
                    }
                }

                ret.push_back(value);

                copied[y1][x1] = 0;
                copied[y2][x2] = 0;
                copied[y3][x3] = 0;
            }
        }
    }
    int mx = 0;
    for (int val : ret){
        mx = max(val, mx);
    }
    cout << mx << "\n";

    return 0;
}

1. 입력이 크지 않아서 무식하게 풀어보려고 도전했음.
2. 3중 for 루프 돌리면서 하나씩 벽 세우고 바이러스 퍼지도록 DFS하였음
3. 바이러스 다 퍼지고 다시 한번 DFS했음
4. 아직 구현중

풀이 (SUCCESS)

#include<bits/stdc++.h>
using namespace std;
int n, m;
int a[10][10], visited[10][10], copied[10][10];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
vector<int> ret;

int dfs(int y, int x, bool virus){
    int result = 1;
    visited[y][x] = 1;

    if(virus){
        copied[y][x] = 2;
    }

    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(visited[ny][nx] == 0 && copied[ny][nx] == 0){
            result += dfs(ny, nx, virus);
        }
    }
    return result;
}

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

    cin >> n >> m;

    vector<pair<int, int>> virus_pos;
    vector<pair<int, int>> zero_pos;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++){
            cin >> a[i][j];
            if(a[i][j] == 2){
                virus_pos.push_back({i, j});
            }

            if(a[i][j] == 0){
                zero_pos.push_back({i, j});
            }
        }
    }

    // 벽 세울 세곳 선택
    for (int i = 0; i < zero_pos.size(); i++){

        if(a[zero_pos[i].first][zero_pos[i].second] != 0){
            continue;
        }

        for (int j = i + 1; j < zero_pos.size(); j++){
            if(a[zero_pos[j].first][zero_pos[j].second] != 0){
                continue;
            }

            for (int k = j + 1; k < zero_pos.size(); k++){
                if(a[zero_pos[k].first][zero_pos[k].second] != 0){
                    continue;
                }

                for (int q = 0; q < n; q++){
                    for (int w = 0; w < m; w++){
                        copied[q][w] = a[q][w];
                    }
                }
                memset(visited, 0, sizeof(visited));

                // 벽 세우기
                int y1, x1, y2, x2, y3, x3;
                tie(y1, x1) = zero_pos[i];
                tie(y2, x2) = zero_pos[j];
                tie(y3, x3) = zero_pos[k];

                copied[y1][x1] = 1;
                copied[y2][x2] = 1;
                copied[y3][x3] = 1;

                // 바이러스 퍼트리기 - 2를 기준으로 DFS
                for(auto coord : virus_pos){
                    dfs(coord.first, coord.second, true);
                }

                memset(visited, 0, sizeof(visited));

                int val = 0;

                for (int q = 0; q < n; q++){
                    for (int w = 0; w < m; w++){
                        if(copied[q][w] != 0 || visited[q][w]){
                            continue;
                        }
                        val += dfs(q, w, false);
                    }
                }

                ret.push_back(val);
            }
        }
    }

    int mx = 0;
    for(int val : ret){
        mx = max(val, mx);
    }
    cout << mx << "\n";

    return 0;
}

1. 눈물겹다.. 혼자서 풀었음! 골드 4 문제!
2. 0으로 초기화된 빈칸에 대해 좌표들을 벡터에 푸시해둔다.
3. 바이러스의 시작지점인 2값에 대해 이를 갖는 좌표 역시 벡터에 푸시해둔다.
4. 초기에 입력된 연구소 배열은 그대로 유지하고, 해당 값들을 카피한 2차원 배열을 마련해둔다.
5. 빈칸을 갖는 벡터에 대해 3중루프를 돌며 각 좌표들에 대해 1로 벽을 쳐준다.
6. 벽을 치고나서 바이러스 시작지점 좌표로부터 DFS를 돌며 0으로 초기화된 빈칸들을 모두 2로 바꿔버린다.
7. 바이러스 전파를 하는 DFS가 끝나면 0값을 갖는 방들에 대해 DFS를 한번 더 진행하며 안전영역을 계산한다.
8. memset으로 visited를 적절히 초기화 해줘야 한다.

모범답안