[C++] BJO 17142 : 연구소 3

문제

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

 

 

풀이

조합 + BFS로 풀었다.

비활성화 바이러스의 수 중 m개의 바이러스를 뽑는 조합 함수를 구현하고,

m개를 뽑을 때마다 해당 m개를 이용해 바이러스를 전파시키는 BFS를 구현하여 풀었다.

 

자세한 풀이는 아래 코드의 주석을  확인하면 된다.

 

단 주의해야 할 점은 지금 문제에서 해야 할 것은 "빈 공간"에 바이러스를 퍼뜨리는 데에 걸리는 최소 시간이지,

비활성화된 바이러스를 모두 활성화시키는 데에 걸리는 시간이 아니라는 것이다.

(이 부분을 처음에 잘못 이해해서 테케를 틀렸다.)

 

 

코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

struct State{
    int y, x, t;
};

struct Idx{
    int y, x;
};

int lab[51][51];
int n,m, answer = -1, cnt = 0;
int dy[] = {0,0,1,-1};
int dx[] = {1,-1,0,0};

vector<Idx> v;
int visited[51][51]; // 방문 표시

Idx id[11];
void combi(int depth, int next_idx){
    
    // 조합 구해진 경우 BFS 수행
    if(depth == m){
        
        queue<State> q;
        int ans = 0; // 현재까지 감염시킨 개수
        int min_t = 0; // 현재까지의 시간
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++) visited[i][j] = 0;
        }

        // 현재 id의 모든 원소를 q에 집어넣고 시작  + 방문 표시
        for(int i=0; i<m; i++){
            q.push({id[i].y, id[i].x, 0});
            visited[id[i].y][id[i].x] = 1;
        }
        
        while(!q.empty()){
            State cur = q.front();
            q.pop();
            
            // 만약 현재 위치가 빈 공간이라면, ans 증가
            if(lab[cur.y][cur.x] ==0){
                ans++;
                min_t = max(min_t, cur.t);
                // 모든 바이러스를 감염시켰다면, answer 업데이트하고 BFS 종료
            }
            
            
            if(ans == cnt){
                    if(answer == -1) answer = min_t;
                    else{
                        answer = min(min_t, answer);
                    }
                    break;
            }

            // 추가 탐색 진행 
            for(int i=0; i<4; i++){
                int ny = cur.y + dy[i];
                int nx = cur.x + dx[i];
                
                if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue; // 범위 초과 
                if(visited[ny][nx] == 1) continue; // 중복 방문 
                if(lab[ny][nx] == 1) continue;  // 벽은 방문 불가능
                
                q.push({ny,nx,cur.t+1});
                visited[ny][nx] = 1;
            }
        }
        return;
    }
    
    else{
        for(int i=next_idx; i<v.size(); i++){
            id[depth] = v[i];
            combi(depth+1, i+1);
        }
    }
}

int main()
{
    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) v.push_back({i,j});
            if(lab[i][j] == 0) cnt++; // 전파해야 할 공간의 수 
        }
    }
    
    combi(0,0);
    cout << answer << "\n";
    return 0;
}

 

 

 

---

메모

조합을 연습하기에 좋은 문제였던 것 같다!
그리고 문제 잘 읽기...