백준 #14502 연구소

백준 #14502 연구소

연구소에 벽을 세 개 세울 수 있는데, 세 개를 세울 수 있는 모든 경우의 수에 대해 바이러스가 퍼진 연구소를 BFS로 계산해 안전 영역의 최댓값을 출력하면 된다.

벽을 세우는 조합은 재귀함수로 처리했다.

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>

using namespace std;

int N, M;
int board[8][8];
bool visited[8][8];
vector<pair<int, int>> initialVirus;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int maxSafe = -1;
bool isInBoard(int nX, int nY);//좌표가 범위 안인지 판별
void makeWall(vector<pair<int, int>> walls, int startX, int startY); //벽을 조합하는 함수
void virusSpread(int** copyBoard); //바이러스를 퍼지게 하는 함수
void copyBoard(int ** board, int ** copiedBoard); //연구소 배열을 복사하는 함수

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> board[i][j];
            if(board[i][j] == 2) {
                initialVirus.push_back({i, j});
            }
        }
    }
    vector<pair<int, int>> walls;
    makeWall(walls, 0, 0);
    cout << maxSafe;
    return 0;
}

bool isInBoard(int nX, int nY) {
    return nX >= 0 && nX < N && nY >= 0 && nY < M;
}

void copyBoard(int ** copiedBoard) {
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            copiedBoard[i][j] = board[i][j];
        }
    }
}

void makeWall(vector<pair<int, int>> walls, int curX, int curY) {
    if(walls.size() == 3) {   //연구소 벽을 세 개 세웠을 때
        int ** copiedBoard = new int*[N];
        for(int i = 0; i < N; i++) {
            copiedBoard[i] = new int[M];
        }
        copyBoard(copiedBoard);  //copiedBoard라는 새로운 연구소 배열에 복사
        for(int i = 0; i < walls.size(); i++) {
            copiedBoard[walls[i].first][walls[i].second] = 1;
        }                        //walls에 저장된 새로운 벽의 조합을 copiedBoard에 적용한다
        memset(visited, 0, sizeof(visited));
        virusSpread(copiedBoard);//바이러스를 퍼뜨린다
        int safePlace = 0;
        for(int i = 0; i < N; i++) {  //안전영역 세기
            for(int j = 0; j < M; j++) {
                if(copiedBoard[i][j] == 0) {
                    safePlace++;
                }
            }
        }
        maxSafe = max(maxSafe, safePlace); //최대 안전영역 최신화
        for(int i = 0; i < N; i++) {
            delete[] copiedBoard[i];
        }
        delete[] copiedBoard;
        return;
    }
    if(!isInBoard(curX, curY)) {
        return;
    }
    int nextX = curX;
    int nextY = curY + 1;
    if(nextY == M) {
        nextY = 0;
        nextX++;
    }
    
    if(board[curX][curY] == 0) {
        walls.push_back({curX, curY});
        makeWall(walls, nextX, nextY);
        walls.pop_back();
    }
    makeWall(walls, nextX, nextY);
    
}

void virusSpread(int ** copiedBoard) {
    queue<pair<int, int>> q;
    for(int i = 0; i < initialVirus.size(); i++) {  //연구소 배열을 입력받을 때 저장한 바이러스의 위치를 전부 큐에 넣는다
        visited[initialVirus[i].first][initialVirus[i].second] = true;
        q.push({initialVirus[i].first, initialVirus[i].second});
    }
    while(!q.empty()) {
        pair<int, int> tmp = q.front();
        copiedBoard[tmp.first][tmp.second] = 2;
        q.pop();
        for(int i = 0; i < 4; i++) {
            int nX = tmp.first + dx[i];
            int nY = tmp.second + dy[i];
            if(isInBoard(nX, nY) && !visited[nX][nY] && copiedBoard[nX][nY] == 0) { //인접한 칸이 0일 때 큐에 넣는다
                q.push({nX, nY});
                visited[nX][nY] = true;
            }
        }
    }
}