[삼성SW테스트] 백준 17142번 연구소 3

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

17142번: 연구소 3

삼성 SW 역량테스트 기출문제이다.

바이러스의 존재 가능 위치와 실제 놓는 위치에 대한 next_permutation 함수의 활용으로 브루트포스로 풀 수 있었다.

놓을 수 있는 모든 경우의 수에 대해 최소시간을 확인해야 정답을 구할 수 있으므로 다른 트릭을 사용하라는 문제는 아니었다. 다만 문제를 꼼꼼히 봐서 비활성 바이러스를 감염시키지 않고 빈 공간을 모두 오염시켰을 경우 바로 시간 카운트를 종료해야하는 부분과 같이 세심한 코딩이 필요한 문제였다.

 

#include  <iostream>
#include  <queue>
#include  <algorithm>
#include  <vector>
#define maxlen 50 
using namespace std; 
 
typedef struct dir{ 
int dx, dy; 
}dir; 
dir direction[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } }; 
 
int N, M; 
int empty_space = 0, empty_space_copy = 0; 
int num_whole_virus = 0; 
int arr[maxlen][maxlen]; 
int Copy[maxlen][maxlen]; 
vector<pair<int, int> > virus; // 바이러스 시작 위치. 
vector combination; // 바이러스 시작 위치 조합. 
vector answers; 
void Copy2arr(){ 
for (int i = 0; i < N; i++){ 
for (int j = 0; j < N; j++){ 
Copy[i][j] = arr[i][j]; 
} 
} 
} 
 
void bfs(){ 
queue<pair<int, int> > q; 
for (int i = 0; i < combination.size(); i++){ 
if (combination[i]){ 
q.push(make_pair(virus[i].first, virus[i].second)); 
} 
} 
int time = 0; 
while (!q.empty()){ 
int size = q.size(); 
for (int i = 0; i < size; i++){ 
int front_x = q.front().first; 
int front_y = q.front().second; 
Copy[front_x][front_y] = 3; 
q.pop(); 
for (int j = 0; j < 4; j++){ 
int next_x = front_x + direction[j].dx; 
int next_y = front_y + direction[j].dy; 
if (next_x >= 0 && next_x < N && next_y >= 0 && next_y < N){ 
if (Copy[next_x][next_y] != 3 && Copy[next_x][next_y] != 1){ 
if (Copy[next_x][next_y] == 0){ 
empty_space_copy--; 
Copy[next_x][next_y] = 3; 
q.push(make_pair(next_x, next_y)); 
} 
else if (Copy[next_x][next_y] == 2){ 
Copy[next_x][next_y] = 3; 
q.push(make_pair(next_x, next_y)); 
} 
} 
} 
} 
} 
time++; 
if (empty_space_copy == 0){ 
break; 
} 
} 
if (empty_space_copy > 0){ 
answers.push_back(-1); 
} 
else 
answers.push_back(time); 
 
// 원상복구 
empty_space_copy = empty_space; 
Copy2arr(); 
} 
 
int main(){ 
ios_base::sync_with_stdio(0); 
cin.tie(0); 
cout.tie(0); 
 
cin >> N >> M; 
for (int i = 0; i < N; i++){ 
for (int j = 0; j < N; j++){ 
cin >> arr[i][j]; 
Copy[i][j] = arr[i][j]; 
if (arr[i][j] == 0){ 
empty_space++; 
empty_space_copy++; 
} 
else if (arr[i][j] == 2){ 
num_whole_virus++; 
virus.push_back(make_pair(i, j)); 
} 
} 
} 
if (empty_space == 0){ 
cout << 0 << '\n'; 
return 0; 
} 
combination.assign(num_whole_virus, 0); 
for (int i = 0; i < M; i++){ 
combination[i] = 1; 
} 
sort(combination.begin(), combination.end()); 
 
do{ 
bfs(); 
} while (next_permutation(combination.begin(), combination.end())); 
sort(answers.begin(), answers.end()); 
for (int i = 0; i < answers.size(); i++){ 
if (answers[i] != -1) 
{ 
cout << answers[i] << '\n'; 
return 0; 
} 
} 
cout << -1 << '\n'; 
return 0; 
}