[17141] 연구소 2

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

17141번: 연구소 2

<문제>

바이러스를 놓은 시점부터 생각해보면, 단순한 level-based bfs를 돌려주면 된다.

정확한 명칭은 모르겠는데, turn이 바뀌는 시점을 일일히 bfs 안에서 체크할 필요가 없이, bfs에서 사용하던

while(!q.empty())안에 sz=q.size(), while(sz--)를 한번 더 중첩하여 간단하게 구현할 수 있다.

바이러스를 놓는 경우의 수는 최악의 경우에 10C5정도, V+E도 3000을 넘지 않으니 브루트포스가 가능하다.

초기에 a[i][j]==2인 지점을 미리 별도의 자료구조에 넣어둔 뒤, 이를 바탕으로 next_permutation()을 진행해주었다. 

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
vector<pi> v;
int n, m, total, ans = 54321, a[51][51], dy[4] = {0, 1, 0, -1},
                 dx[4] = {1, 0, -1, 0};
typedef struct {
    int y, x, turn;
} state;
int f(vector<int> init) {
    queue<state> q;
    bool vst[51][51] = {0};
    int i, ret = 0, S = init.size(), vstCnt = m;
    for (i = 0; i < S; i++)
        if (init[i] == 1) {
            q.push({v[i].first, v[i].second, 0});
            vst[v[i].first][v[i].second] = true;
        }
    while (!q.empty()) {
        int sz = q.size();
        while (sz--) {
            auto cur = q.front();
            q.pop();
            for (i = 0; i < 4; i++) {
                int y = cur.y + dy[i];
                int x = cur.x + dx[i];
                if (y < 0 || x < 0 || y >= n || x >= n || a[y][x] == 1)
                    continue;
                if (vst[y][x] == false) {
                    vst[y][x] = true;
                    q.push({y, x, cur.turn + 1});
                    vstCnt++;
                }
            }
        }
        ret += (q.empty() == false);
    }
    return vstCnt == total ? ret : 54321;
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    int i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) {
            cin >> a[i][j];
            if (a[i][j] == 2) v.push_back({i, j});
            total += (a[i][j] != 1);
        }
    vector<int> base(v.size(), 0);
    for (i = 0; i < m; i++) base[i] = 1;
    sort(base.begin(), base.end());
    do ans = min(f(base), ans);
    while (next_permutation(base.begin(), base.end()) == true);
    if (ans == 54321) ans = -1;
    cout << ans;
    return 0;
}