2382. [모의 SW 역량테스트] 미생물 격리

 

출처 https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

 

 

무작정 BFS 하면 군집이 합쳐 졌을 때 언제가 마지막이 되는지 모르므로 queue에 push를 못함.

따라서 vector를 이용한 DFS를 구현해야 하는데 또 여기서 중요한 점은 하나의 군집씩 끝까지 이동,

끝까지 이동 , 끝까지 이동 이렇게 간다면 같은 순간에 이를테면 첫번째 개체가 갔다가 돌아오는 경우와

두번째 개체가 떠나려고 하는 경우 첫번째 개체를 끝까지 진행하고 두번째로 나아간다면 두번째 개체가 아직 자리에 남아있는 것으로 보일 수 있기 때문에 병렬적으로 처리해 줘야함.

 

 

#include <iostream>
#include <vector>

using namespace std;

int N, M ,K;
int tc;



struct Node{


int y;
int x;
int num;
int dir;
};



int main(void)
{

cin >> tc;

for(int i  = 1; i<= tc; i++)
{

cin >> N >> M >> K;

vector <int>vec[100][100];  // N*N으로 대입하면 런타임 오류 발생 !
int total = 0;

Node arr[K+1];


for(int j = 1; j<=K; j++)
{

cin >> arr[j].y >> arr[j].x >> arr[j].num >> arr[j].dir;
vec[arr[j].y][arr[j].x].push_back(j);
}


    while(M--)
    {
    
     //병렬적으로 초기화 , 이동 , 계산 하지 않으면 하나의 개체씩 움직인다고 생각 했을 때 같은 time에 대해서 다음 개체가 그 자리에 남아있다고 판단될 수 있음. 
    
     for(int j = 1; j <=K; j++)
     {
    
     if (arr[j].num == 0) continue;
vec[arr[j].y][arr[j].x].clear();

//합쳐져서 이동 하든 혼자 이동하든 기존의 위치는 비어지게 됨. 
}
    
    
    
     for(int j = 1; j <=K; j++)
     {
    
    



     if (arr[j].num == 0) continue;
    
    
     if(arr[j].dir == 1)
     {
     arr[j].y -= 1;
}
else if(arr[j].dir == 2)
     {
     arr[j].y += 1;
}
else if(arr[j].dir == 3)
     {
     arr[j].x -= 1;
}
else if(arr[j].dir == 4)
     {
     arr[j].x += 1;
}

vec[arr[j].y][arr[j].x].push_back(j);
   }
   
    for(int j = 1; j <=K; j++)
{

if (arr[j].num == 0) continue;
if(arr[j].x == 0 || arr[j].y == 0 || arr[j].x == N-1 || arr[j].y == N-1)
{
if(arr[j].dir == 1)
           {
     arr[j].dir = 2;
     arr[j].num /= 2;
    }
    else if(arr[j].dir == 2)
         {
     arr[j].dir = 1;
     arr[j].num /= 2;
    } 
    else if(arr[j].dir == 3)
         {
     arr[j].dir = 4;
     arr[j].num /= 2;
      }
else if(arr[j].dir == 4)
         {
     arr[j].dir = 3;
     arr[j].num /= 2;
    }




}
else{



if(vec[arr[j].y][arr[j].x].size() > 1)
{


int max = 0;
int dir;
int index;

int sum = 0;

for(int s = 0; s<vec[arr[j].y][arr[j].x].size(); s++)
{
sum += arr[vec[arr[j].y][arr[j].x][s]].num;

if(max < arr[vec[arr[j].y][arr[j].x][s]].num)
{
max = arr[vec[arr[j].y][arr[j].x][s]].num;
index = vec[arr[j].y][arr[j].x][s];
dir = arr[index].dir;
}

arr[vec[arr[j].y][arr[j].x][s]].num = 0;
//0이된 군집은 모든 과정에서 무시하도록 처리.
 } 
 
 arr[index].num = sum;
 arr[index].dir = dir;
 
 
}



}

}
    
     //time 변수를 이용해서 시간 조절을 하는게 아니고 병렬처리로 같은 시간임을 나타내야 함. 
    
    
    
    
    
    
    
    
}
    
    
    








for(int b = 1; b<=K; b++)
{

total += arr[b].num;
}





cout<<"#"<<i<<" "<<total<<endl;
}



}