[Algorithm] 백준 14502번 연구소

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

백준 14502번 연구소

이거는 그냥 맵 크기가 작기 때문에 전부 다 찾고, 전부 다 돌려보면 됨.

흔히 말하는 완전탐색

자기 전에 빠르게 짜보기 위해 엄청 대충 짰기 때문에 다시 한번 정신이 말짱할 때 깔끔하게

그리고 변수 크기가 커져도 제한 시간 내에 작동할 수 있도록 수정을 해봐야 겠다.

문제 풀이

1. 벽을 "무조건" 3개 설치 해야함.

2. 바이러스는 벽을 뚫지 못함.

3. 바이러스가 퍼지지 않은 안전 지대의 영역 크기를 구해야 함.

  → 전체적으로 맵 크기가 작기 때문에, for문 돌면서 간단하게 풀어도 잘 풀림. (추후 수정 예정)

#include <iostream>
#include <vector>
 
using namespace std;
int N, M, result = -1;
int gCnt, oCnt;
vector < vector < int > > map;
vector < vector < int > > visit;
vector < vector < int > > visitOrigin;
vector < vector < int > > temp;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
void polluteProcess(int x, int y) {
    if (gCnt <= 0) return;
    if (gCnt <= result) return;
    for (int i = 0; i < 4; i++) {
        int cx = x + dx[i];
        int cy = y + dy[i];
        if (cx >= 0 && cy >= 0 && cx < N && cy < M) {
            if (map[cx][cy] != 1 && visit[cx][cy] == 0) {
                map[cx][cy] = 2;
                visit[cx][cy] = 1;
                gCnt--;
                polluteProcess(cx, cy);
            }
        }
    }
}
void pollute() {
    visitOrigin = visit;
    temp = map;
    gCnt = oCnt - 3;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 2) {
                polluteProcess(i, j);
            }
        }
    }
    if (result < gCnt) result = gCnt;
    map = temp;
    visit = visitOrigin;
}
void dfs(int x, int cnt) {
    if (cnt == 3) {
        pollute();
        return;
    }
    for (int i = x; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 0) {
                map[i][j] = 1;
                visit[i][j] = 1;
                dfs(i, cnt + 1);
                map[i][j] = 0;
                visit[i][j] = 0;
            }
        }
    }
}
int main()
{
    cin >> N >> M;
    map.assign(N + 1, vector<int>(M + 1, 0));
    visit.assign(N + 1, vector<int>(M + 1, 0));
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
            if (map[i][j] != 0) {
                visit[i][j] = 1;
            }
            else {
                gCnt++;
            }
        }
    }
    oCnt = gCnt;
    dfs(0,0);
 
    cout << result;
    return 0;
}