문제 출처 : 연구소3_17142
파라미터 정리
NxN 연구소 (4~50)
M : 활성화된 바이러스 수 (1~10)
0 : 빈 칸
1 : 벽
2 : 바이러스를 놓을 수 있는 위치 (M~10)
바이러스는 1초에 인접한 상하좌우로 전파됨
원하는 것 = 모든 바이러스 중 M개의 바이러스가 활성화될 때 모든 공간에 바이러스가 퍼지는 최소 시간 출력하기
어떠한 경우에도 모든 빈칸에 바이러스를 놓을 수 없는 경우 return -1
간략한 과정
input_1 N, M 입력받기
input_2 초기 맵정보 Map[50][50] 입력받기
바이러스 위치(2)의 정보 배열에 저장 (r,c 필요)
빈 칸(0)의 개수 저장 (empty_size)
int res = INF;
shift 연산자 이용해서 모든 경우의 수 만들기
M개가 선택되었을 때 시뮬레이션 진행하기{
do{} while(empty_size>0) 빈 칸이 없어질 때까지
(고민중_breakpoint : cnt >55 // 이전 e_s와 현재 e_s가 같으면 변화없으므로)
1초마다 상하좌우 바이러스 확산시키기
(이 때 셀 범위 벗어났는 지 확인하기)
Queue 이용해서 생성된 순서대로 (바이러스 위치, 시간) 넣기
int cnt = 현재 Queue에서 가져온 인자의 시간
empty_size == 0이면 res = min(res,cnt) 비교하기
}
output 반환값이 INF라면 -1 반환, 아니면 그 값을 최종적으로 반환
코드
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 98456215
struct loc{
int r,c,d;
};
int N,M;
int Map[50][50];
loc Virus[10];
int VirusCnt;
int Dr[4] = {-1,1,0,0};
int Dc[4] = {0,0,-1,1};
int checkBit(int n){
int cnt = 0;
while (n) {
if (n & 1) ++cnt;
n = n >> 1;
}
return cnt;
}
int solve(){
int res = INF;
for(int subset = 0; subset < 1<<VirusCnt; subset++){
//바이러스 수가 virus 벡터만큼 있을 때 발생하는 모든 경우의 수
if(checkBit(subset) == M){
bool visited[50][50] = {false};
int dist = 0;
queue<loc> myqueue;
for(int i = 0; i < VirusCnt; i++){
if(subset & 1<<i){
visited[Virus[i].r][Virus[i].c] = true;
myqueue.push(Virus[i]);
}
}
//BFS 탐색
while(!myqueue.empty()){
loc curr = myqueue.front();
myqueue.pop();
if(Map[curr.r][curr.c] != 2)
dist = max(dist, curr.d);//여기 이해 안됨
for(int i = 0; i < 4; i++){
int nr = curr.r + Dr[i], nc = curr.c + Dc[i];
if(nr < 0 || nc < 0 || nr > N-1 || nc > N-1) continue;
if(visited[nr][nc] || Map[nr][nc] == 1) continue;
visited[nr][nc] = true;
myqueue.push({nr, nc, curr.d + 1});
}
}
bool flag = true;
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
if(Map[i][j] == 0 && visited[i][j] == false)
flag = false;
if(flag)
res = min(res,dist);
}
}
if(res == INF) return -1;
return res;
}
int main()
{
cin >> N >> M;
VirusCnt = 0;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
cin >> Map[i][j];
if(Map[i][j] == 2)
Virus[VirusCnt++] = {i,j};
}
}
cout << solve() << endl;
return 0;
}다른 풀이
백업_0603_pm07:30
예제 통과함
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 98456758
struct loc{
int r,c,d;
};
int N,M;
int Map[50][50];
vector<loc> virus;
int Dr[4] = {0,-1,0,1};
int Dc[4] = {1,0,-1,0};
bool checkBlank(){
bool flag = true;
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
if(Map[i][j] == 0) flag = false;
return flag;
}
int checkBit(int n){
int res = 0;
do{
if(n & 1) res++;
n = n >> 1;
}while(n>0);
return res;
}
int solve(){
int res = INF;
for(int i = 0; i < (1<<virus.size()); i++){
if(checkBit(i) == M){
queue<loc> locque;
int backup[50][50];
memcpy(backup,Map,sizeof(Map));
int dist = 0;
for(int j = 0; j < virus.size(); j++){
if(i & (1<<j)){
locque.push(virus[i]);
Map[virus[j].r][virus[j].c] = 9;
}
}
do{
loc curr = locque.front();
locque.pop();
dist = max(dist,curr.d);
for(int i = 0; i < 4; i++){
int nr = curr.r + Dr[i], nc = curr.c + Dc[i];
if(Map[nr][nc] != 0) continue;
if(nr < 0 || nc < 0 || nr > N-1 || nc > N-1) continue;
Map[nr][nc] = curr.d+1;
locque.push({nr,nc,curr.d+1});
}
}while(!locque.empty());
if(checkBlank()) res = min(res,dist);
memcpy(Map,backup,sizeof(Map));
}
}
if(res == INF) return -1;
else return res;
}
int main()
{
cin >> N >> M;
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,0});
}
}
cout << solve() << endl;
return 0;
}시행착오
백업_0529_pm09
->무브에 갇혀있음 지금 방법은 바이러스 한칸씩 이동시킨후 그때마다 emptysize 변화값 확인하는 중,,,다른 방법 없을지 고민해보기
->잘모르겠음, 내일 다시 풀어보기
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 98456154
struct loc{
int r,c,sec;
};
int N, M;
int Map[50][50];
int empty_size = 0;
queue<loc> virus;
int Dr[4] = {0,1,0,-1};
int Dc[4] = {1,0,-1,0};
void move(loc input){
int nr = input.r, nc = input.c, nt = input.sec;
if(Map[nr][nc] == 0){
Map[nr][nc] = 2;
empty_size--;
}
for(int i = 0; i < 4; i++){
nr += Dr[i];
nc += Dr[i];
if(nr < 0 || nc < 0 || nr > N-1 || nc > N-1) continue;
if(Map[nr][nc] == 1 || Map[nr][nc] == 2) continue;
virus.push({nr,nc,nt+1});
}
return;
}
int bit_check(int input){
int cnt = 0;
do{
if(input & 1) cnt++;
input = input >> 1;
}while(input>0);
return cnt;
}
int solve(){
int res = INF;
int v_size = virus.size();
for(int i = 0; i < (1 << v_size); i++){
if(bit_check(i) == M){//M개의 바이러스가 활성화 되었을 때
//memcpy
//빈 칸이 없어질 때까지 바이러스 확산
int cnt = 0;
do{
loc curr = virus.front();
virus.pop();
cnt = curr.sec;
move(curr);
}while(!virus.empty() || empty_size!=0);
res = min(res, cnt);
//memcpy
}
}
return res;
}
int main()
{
cin >> N >> M;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
cin >> Map[i][j];
if(Map[i][j] == 0) empty_size++;
else if(Map[i][j] == 2) virus.push({i,j,0});
}
}
cout << solve() << endl;
return 0;
}
열심히!