[CodeTree] 방화벽 설치하기 (C++) [삼성 SW 역량테스트 기출]

https://www.codetree.ai/training-field/frequent-problems/problems/firewall-installation

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n, m, answer;
int map[8][8];
int tmp[8][8];
bool isUsed[64];

int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};

vector<pair<int, int>> blank;
vector<pair<int, int>> fire;

void bfs(int x, int y){
    queue<pair<int, int>> q;
    q.push({x, y});

    while(!q.empty()){
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++){
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            if(nx >= 0 && ny >= 0 && nx < n && ny < m && tmp[nx][ny] == 0){
                tmp[nx][ny] = 2;
                q.push({nx, ny});
            }
        }
    }
}

void dfs(int depth, int start){
    if(depth == 3){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                tmp[i][j] = map[i][j];
            }
        }
        for(int i = 0; i < fire.size(); i++){
            bfs(fire[i].first, fire[i].second);
        }
        int cnt = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(tmp[i][j] == 0) cnt++;
            }
        }
        answer = max(answer, cnt);
    } else{
        for(int i = start; i < blank.size(); i++){
            if(!isUsed[i]){
                isUsed[i] = true;
                map[blank[i].first][blank[i].second] = 1;
                dfs(depth + 1, start + 1);
                map[blank[i].first][blank[i].second] = 0;
                isUsed[i] = false;
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> map[i][j];
            if(map[i][j] == 0) blank.push_back({i, j});
            else if(map[i][j] == 2) fire.push_back({i, j});
        }
    }

    dfs(0, 0);

    cout << answer;
    return 0;
}