백준 14502 - 연구소 (c++)

백준 14502 - 연구소

문제 링크

생각 및 접근

• 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다에서 바이러스가 퍼져나가는 것을 BFS 방식으로 시뮬레이션을 돌려야겠다 고 생각했다.
• BFS하기 전에, 벽 3개를 셋팅해주어야 한다.
  • 배열에서 바이러스 부분(값이 2인 부분)을 vector<pair<int, int>> virus;로 받는다.
  • 배열에서 빈 부분(값이 0인 부분)을 vector<pair<int, int>> emp;로 받는다.
    • 빈 부분을 Combination한다.

      • 

      • Combination을 조금 야매 방식으로 했는데,
        • vector<int> comb;에 골라야 할 갯수만큼 1을, (전체 갯수 - 골라야 할 갯수)만큼 0을 추가한다.
        • 오름차순으로 comb을 sort한다.
        • next_permutation을 돌린다. comb에서 1인 값들을 찾으면 그 index가 Combination의 결과다.
• BFS를 통해 바이러스를 전파 시키고, temp에서 0의 갯수를 세어주면 그 값이 답의 후보가 된다. 가장 큰 값을 기억해준다. (answer)

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, answer = -1;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<vector<int>> arr;
vector<pair<int, int>> virus;
vector<pair<int, int>> emp;
vector<int> comb;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;
    arr.assign(n + 2, vector<int>(m + 2, 0));

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> arr[i][j];
            if(arr[i][j] == 2)    virus.push_back(make_pair(i, j));
            if(arr[i][j] == 0)    emp.push_back(make_pair(i, j));
        }
    }

    for(int i = 1; i <= emp.size() - 3; i++)
        comb.push_back(0);
    for(int i = 1; i <= 3; i++)
        comb.push_back(1);

    sort(comb.begin(), comb.end());

    do {
        queue<pair<int, int>> q;
        vector<vector<int>> temp = arr;
        vector<pair<int, int>> wall;
        int cnt = 0;

        for(int i = 0; i < comb.size(); i++){
            if(comb[i] == 1)
                wall.push_back(emp[i]);
        }

        for(int i = 0; i < 3; i++)
            temp[wall[i].first][wall[i].second] = 1;
        for(auto v : virus)
            q.push(v);

        while(!q.empty()){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();

            temp[x][y] = 2;
            for(int i = 0; i < 4; i++){
                int xx = x + dx[i];
                int yy = y + dy[i];

                if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && temp[xx][yy] == 0)
                    q.push(make_pair(xx, yy));
            }
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(temp[i][j] == 0)    cnt++;
            }
        }

        answer = max(answer, cnt);

    } while(next_permutation(comb.begin(), comb.end()));

    cout << answer;
}

채점 결과