백준 17142번 연구소 3 - C++ 풀이

---

 

1. M개의 자리를 활성시키는 모든 경우를 시뮬레이션하여 최소 시간을 구한다.
2. 각 경우는 BFS를 이용해서 시뮬레이션한다.

 

1. M개의 자리를 활성시키는 모든 경우를 시뮬레이션하여 최소 시간을 구한다.

 바이러스를 놓을 수 있는 위치가 최대 10군데이고, M이 최대 10이므로 최악의 경우에도 10C5가지 경우 밖에 발생하지 않는다. 또한 각 경우를 시뮬레이션하는 데는 O(N^2)의 시간 복잡도가 들기 때문에 브루트 포스를 사용해도 충분하다.

 

2. 각 경우는 BFS를 이용해서 시뮬레이션한다.

 바이러스가 퍼지는 시뮬레이션은 BFS를 사용하면 쉽게 구현할 수 있다.

 

반응형

---

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
typedef pair<int, int> pii;
const int EMPTY = 0, WALL = 1, AVAILABLE = 2;
const int INF = 987654321;

int N, M;
int board[50][50];
vector<pii> availables;

int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

int simulate(vector<pii> virus) {
    int ret = 0;
    vector<vector<int>> visit(N, vector<int>(N, INF));
    queue<pii> q;
    
    for (auto v: virus) {
        q.push(v);
        visit[v.first][v.second] = 0;
    }
    
    while (!q.empty()) {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        
        for (int i=0; i<4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            
            if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
            if (board[nr][nc] == WALL) continue;
            if (visit[nr][nc] != INF) continue;
            
            visit[nr][nc] = visit[r][c] + 1;
            q.push({nr, nc});
        }
    }
    
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            if (board[i][j] != EMPTY) continue;
            ret = max(ret, visit[i][j]);
        }
    }
    
    return ret;
}

int bruteForce(int idx, vector<pii> pick) {
    if (idx == availables.size()) {
        return (pick.size() == M) ? simulate(pick) : INF;
    }
    
    int ret = INF;
    
    ret = min(ret, bruteForce(idx+1, pick));
    pick.push_back(availables[idx]);
    ret = min(ret, bruteForce(idx+1, pick));
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cin >> board[i][j];
            if (board[i][j] == AVAILABLE) {
                availables.push_back({i, j});
            }
        }
    }
    
    int ans = bruteForce(0, {});
    
    if (ans == INF) cout << -1;
    else cout << ans;

    return 0;
}