[BFS 알고리즘] 연구소 ★★☆

기출 : 삼성전자 SW 역량테스트

 

전형적인 삼성 BFS 문제이다

 

비어있는 공간 중 3개를 골라 벽을 세우고 바이러스를 진행시킨 다음 빈 공간의 갯수를 세어 그 최댓값을 출력한다

 

다른 BFS 문제와 다른 점이 있다면 next_permutation을 사용하여 순열을 계산하는 것이었다

 

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int n, m;
int maxval=-1;
int board[9][9];
vector<pair<int, int>> emty;
vector<pair<int, int>> virus;
vector<int> b;

int BFS(vector<pair<int, int>> v) {
    int cnt=0;
    int tboard[9][9];
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            tboard[i][j] = board[i][j];
        }
    }
    for (int i = 0;i < 3;i++) tboard[v[i].first][v[i].second] = 1;
    queue<pair<int, int>> q;
    for (int i = 0;i < virus.size();i++) {
        q.push(virus[i]);
        while (!q.empty()) {
            pair<int, int> cur = q.front(); q.pop();
            for (int dir = 0;dir < 4;dir++) {
                int mx = cur.X + dx[dir];
                int my = cur.Y + dy[dir];
                if (mx < 0 || my < 0 || mx >= n || my >= m) continue;
                if (tboard[mx][my] != 0) continue;
                tboard[mx][my] = 2;
                q.push({ mx,my });
            }
        }
    }
    for (int i = 0;i < n;i++) {				
        for (int j = 0;j < m;j++) {
            if (tboard[i][j] == 0) cnt++;
        }
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    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] == 0) emty.push_back({ i,j });
            if (board[i][j] == 2) virus.push_back({ i,j });
        }
    }
    for (int i = 0;i < emty.size() - 3;i++) b.push_back(0);
    for (int i = 0;i < 3;i++) b.push_back(1);
    do {
        vector<pair<int, int>> v;
        for (int i = 0;i < b.size();i++) {
            if (b[i]) v.push_back(emty[i]);
        }
        maxval = max(maxval, BFS(v));
    }while(next_permutation(b.begin(),b.end()));
    cout << maxval;
    return 0;
}