[백준 17142] 연구소 3 (C++)

17142번: 연구소 3

BFS

---

삼성 SW 기출

BFS 시뮬레이션 문제! 

 

M은 최대 10개!! 

바이러스도 최대 10개이므로 바이러스를 고를 수 있는 경우의 수는 최대 252개! -> 10C5

연구실의 최대 크기는 50x50 = 2500!!

252 * 2500 하면 약 60만개!!

 

0.25초 안에 해결하기 충분함!

 

바이러스를 고를 수 있는 경우의 수를 백트래킹을 통해서 구하고, 바이러스 M개를 고르면 고른 바이러스들을 가지고 bfs를 돌린다!

 

빈 칸에 도달한 경우에만 답을 갱신한다!

-> 가장 마지막에 바이러스가 퍼지는 경우는 시간을 더해줄 필요가 없기 때문

 

 

다음 바이러스가 퍼질 공간을 찾는데 nr과 nc가 0이상 N미만이어야 하는데 조건을 nr >= N || nr >= N 이렇게 nr만 2번 설정해서 틀렸었다. 정말 문자 하나때문에 틀린것..

만약 코테 치면서 이런 실수하면 정말 슬플듯. 지금은 30분이 걸려서 찾았는데 시험칠때는 어떻게 될까!

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, M, result = INF;
int Lab[51][51];
int dr[4] = {0, 0, 1, -1}, dc[4] = {1, -1, 0, 0};
vector<pii > virus;
 
void input(){
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> Lab[i][j];
            if(Lab[i][j] == 2){
                virus.push_back({i, j});
            }
        }
    }
}
 
int bfs(vector<pii > &vec){
    int tLab[51][51];
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            tLab[i][j] = Lab[i][j];
        }
    }
    int ans = 0;
    queue<pii > que;
    for(auto &w : vec){
        que.push(w);
        tLab[w.first][w.second] = -1;
    }
    
    while(!que.empty()){
        pii now = que.front();
        int now_time = tLab[now.first][now.second];
        que.pop();
        
        
        if(Lab[now.first][now.second] != 2) ans = abs(now_time + 1);
        if(ans >= result) return INF;
        
        for(int k = 0; k < 4; k++){
            int nr = now.first + dr[k];
            int nc = now.second + dc[k];
            
            if(nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
            if(tLab[nr][nc] == 1 || tLab[nr][nc] < 0) continue;
            if(!tLab[nr][nc] || tLab[nr][nc] == 2){
                tLab[nr][nc] = now_time - 1;
                que.push({nr, nc});
            }
        }
    }
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(!tLab[i][j]) return INF;
        }
    }
    return ans;
}
 
void dfs(int now, vector<pii > &vec){
    if(vec.size() == M){
        result = min(result, bfs(vec));
        return;
    }
    for(int i = now; i < virus.size(); i++){
        vec.push_back(virus[i]);
        dfs(i+1, vec);
        vec.pop_back();
    }
}
 
void solve(){
    vector<pii> vec;
    dfs(0, vec);
    
    if(result == INF) cout << -1 << "\n";
    else cout << result << "\n";
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}