백준 17142번 C++

 

삼성 기출문제를 풀어보았다.

연구소 시리즈는 이로써 다 풀었다.

 

이 문제에서의 핵심은 "바이러스는 M개가 있고 그 중 K개를 활성화 하는 경우의 수" 라고 볼 수 있다.

조합을 통해 경우의 수 마다 BFS를 진행해 최단시간의 경우를 구해주면 된다.

 

이 문제를 위해 내가 추천하는 방식은

 mCk 조합 구현을 위해 next_permutation 함수를 사용하는 것이다.

 

next_permutation 함수 알아보기

vector<int> v = {1, 2, 3};

do {
	for(auto o : v) {
    	cout << o << " ";
    } cout << "\n";

} while(next_permutation(v.begin(), v.end()));


출력 :
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1

next_permuation은 주어진 벡터 리스트의 값을 나열하는 경우의 수, 순열을 구할 때 자주 쓰인다.

 

이를 이용해서 mCk 같이, m개의 중에서 k개를 뽑는 경우의 수인 조합도 구할 수 있다.

원리는 임시벡터를 만들어 k개를 1로 채우고, m-k개를 0으로 채운 벡터를 만들어주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    
    vector<int> v = {1, 2, 3};

    int m = 5, k = 2;
    vector<int> tempVector;
    
    for(int i = 0; i < k; i++) {
        tempVector.push_back(1);
    }
    for(int i = 0; i < m - k; i++) {
        tempVector.push_back(0);
    }
    
    sort(tempVector.begin(), tempVector.end());
    
    
    do {
        for(auto o : tempVector) {
            cout << o << " ";
        } cout << "\n";

    } while(next_permutation(tempVector.begin(), tempVector.end()));
}

출력 : 
0 0 0 1 1 
0 0 1 0 1 
0 0 1 1 0 
0 1 0 0 1 
0 1 0 1 0 
0 1 1 0 0 
1 0 0 0 1 
1 0 0 1 0 
1 0 1 0 0 
1 1 0 0 0

그럼 인덱스가 0인 부분이 뽑히지 않은 부분이고, 인덱스가 1인 부분이 뽑힌 부분으로 생각하면 된다.

여기서 중요한 개념이 있는데, next_permuation을 사용할 때에는 무조건 오름 정렬되어있어야 한다.

따라서 sort함수를 써서 처음에 정렬을 한번 진행해 준 것이다.

 

 

문제 풀이

이제 문제로 돌아와서, 이렇게 next_permutation을 이용해서 경우의 수를 만든 다음

활성 바이러스를 BFS 진행하면 되는데, 이 문제를 진행함에 있어 주의할 점이 몇 가지 있다.

 

1. 비활성 바이러스도 바이러스다

즉슨, 비활성 바이러스의 자리 빼고는 모든 자리에 바이러스가 퍼졌다면, 여기서 끝나야 정상이다.

비활성 바이러스까지 가는 시간을 추가해서 +1 초의 무의미한 시간이 없도록 해야한다

 

2. 바이러스가 다 퍼졌을 때의 시간만 유의미하다.

mCk를 하다보면, 바이러스가 다 퍼지지 않는 경우도 분명히 있는데, 이 때 구해진 최단시간을 유의미한 값으로 다뤄줘선 안된다.

 

 

이 두가지를 고려한다면 예외 케이스를 벗어날 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
#define MAX(a,b) ((a >= b) ? a : b)
#define MIN(a,b) ((a <= b) ? a : b)

using namespace std;

int N, K;
int maxDepth, minDepth = 2500;
int virusSize;

int map[50][50];
bool visit[50][50]; // 안쓰고 map으로만 이용해보려 했는데 결국 어쩔 수 없이 필요했다.

int mx[4] = {0, 0, -1, 1};
int my[4] = {1, -1, 0, 0};

vector<pair<int, int>> virus;

bool bfs(vector<int>& activeVirus) { // 리턴값은 모든 곳에 퍼뜨리기 성공여부
    
    queue<pair<pair<int, int>, int>> que;
    
    int tempMap[50][50];
    memcpy(tempMap, map, sizeof(map));
    
    for(auto index : activeVirus) {
        que.push({{virus[index].first, virus[index].second}, 0});
        visit[virus[index].first][virus[index].second] = true;
    }
    
    
    while(!que.empty()) {
        
        
        int x = que.front().first.first;
        int y = que.front().first.second;
        int d = que.front().second;
        
        que.pop();
        
        for(int i = 0; i < 4; i++) {
            
            int tx = x + mx[i];
            int ty = y + my[i];
            
            if(tx < 0 || tx >= N || ty < 0 || ty >= N)
                continue;
            
            
            
            if(!visit[tx][ty] && tempMap[tx][ty] == 0) {
                tempMap[tx][ty] = d + 1;
                que.push({{tx, ty}, d + 1});
            
                maxDepth = MAX(maxDepth, d + 1);
                
                visit[tx][ty] = true;
                
            } else if(!visit[tx][ty] && tempMap[tx][ty] == 2) {
                que.push({{tx, ty}, d + 1});
                visit[tx][ty] = true;
            }
            
        }
        
        
    }
    

    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(tempMap[i][j] == 0)
                return false;
        }
    }

    return true;
}

int main() {
    
    cin >> N >> K;
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> map[i][j];
            if(map[i][j] == 2)
                virus.push_back({i, j});
        }
    }
    
    virusSize = virus.size();
    
    
    // next_permutation 이용해서 조합 만들기 nCk
    vector<int> tempVector;

    for(int i = 0; i < K; i++) tempVector.push_back(1);
    for(int i = 0; i < virusSize - K; i++) tempVector.push_back(0);
    
    // 제일 주의해야할 점 : next_permutaiton을 쓸 때는 항상 무조건. 정렬되어있어야한다.
    sort(tempVector.begin(), tempVector.end());
    
    do {

        vector<int> activeVirus;
        for(int i = 0; i < virusSize; i++) {
            if(tempVector[i] == 1)
                activeVirus.push_back(i); // 활성화된 바이러스 인덱스
        }
        maxDepth = 0;
        memset(visit, 0, sizeof(visit));

        if(bfs(activeVirus)) minDepth = MIN(minDepth, maxDepth);

        
    } while(next_permutation(tempVector.begin(), tempVector.end()));
    
    
    cout << ((minDepth == 2500) ? -1 : minDepth) << "\n";
    
}

 

예외케이스를 잡느라 시간은 상당히 오래 걸렸다.

시험이었으면 떨어졌다.