[백준/Baekjoon] 17142 연구소 3 C++ :: BFS

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

17142번: 연구소 3

---

1. Logic

여기서 주의해야 할 점은 바이러스가 퍼지면서 비활성 바이러스에 닿게 되면 그 부분은 시간으로 처리를 안해준다. 문제에 따로 명시는 되어있지 않지만 테스트 케이스를 설명해주는 그림을 잘 보면 그렇게 되어있다...

 

1. 문제를 푸는 로직은 먼저 입력받으면서 바이러스가 있는 좌표를 저장해놓는다. 

2. 바이러스를 활성화 할 수 있는 갯수가 정해져있기 때문에 조합을 활용해서 m개만큼 활성화 할 바이러스를 뽑아준다.

3. m개만큼 뽑히면 BFS를 들어가서 2번에서 뽑은 바이러스의 좌표를 queue에 넣어주고 BFS를 돌린다

4. 바이러스를 만났을 때는 시간 갱신을 해주지 않고 빈 공간을 만났을 때만 시간 갱신을 해준다.

 

 

 

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int n, m;

int dy[4] = {0, -1, 0, 1};
int dx[4] = {-1, 0, 1, 0};

int graph[51][51];
int vis[51][51];

vector<pair<int, int>> virus;
int virusCheck[11];

int roomCnt = 0;
int ans = 0x3f3f3f3f;

int bfs() {
    queue<pair<int, int>> q;
    memset(vis, -1, sizeof(vis));
    
    for(int i = 0; i < virus.size(); i++) {
        if(virusCheck[i]) {
            int vy = virus[i].first;
            int vx = virus[i].second;
            q.push({vy, vx});
            vis[vy][vx] = 0;
        }
    }
    
    int cnt = 0;
    int t = 0;
    
    while(!q.empty()) {
        int x = q.front().second;
        int y = q.front().first;
        
        q.pop();
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            if(vis[ny][nx] != -1) continue;
            if(graph[ny][nx] == 1) continue;
            
            q.push({ny, nx});
            vis[ny][nx] = vis[y][x] + 1;
            if(graph[ny][nx] == 0) {
                cnt++;
                t = vis[ny][nx];
            }
        }
    }
    if(cnt == roomCnt) return t;
    else return 0x3f3f3f3f;
}

void choice(int idx, int cnt) {
    if(cnt == m) {
        ans = min(ans, bfs());
        return;
    }
    if(idx == virus.size()) return;
    
    for(int i = idx+1; i < virus.size(); i++) {
        if(virusCheck[i]) continue;
        virusCheck[i] = true;
        choice(i, cnt+1);
        virusCheck[i] = false;
    }
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> graph[i][j];
            if(graph[i][j] == 2) {
                virus.push_back({i, j});
            }
            else if(graph[i][j] == 0) {
                roomCnt++;
            }
        }
    }
    
    for(int i = 0; i < virus.size(); i++) {
        virusCheck[i] = true;
        choice(i, 1);
        virusCheck[i] = false;
    }
    
    if(ans == 0x3f3f3f3f) cout << -1;
    else cout << ans;
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐