14502번 : 연구소 - Junnnho

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

14502번: 연구소

이 문제를 해결하는데 필요한 알고리즘 : BFS or Brute force (or DFS)

나는 BFS로 풀었다.

처음에는 배열의 크기를 생각하지 못하고 시간초과 없이 어떻게 해결해야하나 했는데

8*8 크기라면 전범위를 다돌아도 괜찮을 것 같았다.

바이러스가 없는 0 부분에 1을 2칸 집어넣고 1칸씩 옮겨가면서 경우의 수를 다 구해줬다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int arr[8][8];
int ans[8][8];
int Arr[8][8];
int temp[4] = { -1,1,0,0 };
int temp2[4] = { 0,0,-1,1 };
typedef pair<int, int> pii;
vector<pii> v;
int MAX, first, second;
int N, M, virus;
bool visit;
bool check[8][8];
 
void dfs(int n, int m) { // n -> 세로 m -> 가로
 
    for (int i = 0; i < 4; i++) {
        if (n + temp[i] >= 0 && n + temp[i] < N && m + temp2[i] >= 0 && m + temp2[i] < M) {
            if (arr[n + temp[i]][m + temp2[i]] == 0) {
                arr[n + temp[i]][m + temp2[i]] = 2;
                dfs(n + temp[i], m + temp2[i]);
            }
        }
    }
 
}
 
void lab() {
 
    if (virus == 3) {
        int zero = 0;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                ans[i][j] = arr[i][j];
        for (int i = 0; i < v.size(); i++) {
            dfs(v[i].first, v[i].second);
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 0) zero++;
                arr[i][j] = ans[i][j];
                ans[i][j] = Arr[i][j];
            }
        }
        MAX = max(MAX, zero);
        return;
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (i == N-1 && j == M-1) 
                visit = true;
            if (arr[i][j] == 0) {
                if (!check[i][j]) {
                    if (virus == 1)
                        check[i][j] = true, first = i, second = j;
                    arr[i][j] = 1, virus++;
                    lab();
                    if (i != first || j != second)
                        arr[i][j] = 0, virus--;
                }
            }
            if (visit == true) {
                if (i == first && j == second) {
                    visit = false;
                    if (first != N - 1 || second != M - 1) {
                        arr[first][second] = 0, virus--;
                        if (second != M - 1) {
                            j = second;
                        }
                        else {
                            i = first;
                            j = -1;
                        }
                    }
                }
                else return;
            }
        }
    }
}
 
int main() {
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
            Arr[i][j] = arr[i][j];
            if (arr[i][j] == 2) v.push_back(make_pair(i, j));
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == 0) {
                arr[i][j] = 1, virus = 1, visit = false;
                lab();
                if (Arr[N - 1][M - 1] != 1)
                    if (arr[N - 1][M - 1] == 1) arr[N - 1][M - 1] = 0;
                arr[i][j] = 0;
            }
            for (int i = 0; i < N; i++)
                for (int j = 0; j < M; j++)
                    check[i][j] = false;
        }
    }
 
    cout << MAX;
}