[SWEA] 미생물 격리

[문제]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl

SW Expert Academy

[풀이]

 

제출일 : 2019-08-01 15:29

• C++언어
• 12,684 kb메모리
• 879 ms실행시간
• 2,802코드길이
• Pass결과

   ① 최초 각 미생물 군집의 위치와 군집 내 미생물의 수, 이동 방향이 주어진다. 약품이 칠해진 부분에는 미생물이 배치되어 있지 않다. 이동방향은 상, 하, 좌, 우 네 방향 중 하나이다.

   ② 각 군집들은 1시간마다 이동방향에 있는 다음 셀로 이동한다.

   ③ 미생물 군집이 이동 후 약품이 칠해진 셀에 도착하면 군집 내 미생물의 절반이 죽고, 이동방향이 반대로 바뀐다. 
       미생물 수가 홀수인 경우 반으로 나누어 떨어지지 않으므로, 다음과 같이 정의한다.
       살아남은 미생물 수 = 원래 미생물 수를 2로 나눈 후 소수점 이하를 버림 한 값
       따라서 군집에 미생물이 한 마리 있는 경우 살아남은 미생물 수가 0이 되기 때문에, 군집이 사라지게 된다,

   ④ 이동 후 두 개 이상의 군집이 한 셀에 모이는 경우 군집들이 합쳐지게 된다. 
       합쳐 진 군집의 미생물 수는 군집들의 미생물 수의 합이며, 이동 방향은 군집들 중 미생물 수가 가장 많은 군집의 이동방향이 된다. 
       합쳐지는 군집의 미생물 수가 같은 경우는 주어지지 않으므로 고려하지 않아도 된다.
     

* 구하는 값 : M시간 후 남아 있는 미생물 수의 총합을 구하여라.

 

* disable[1001] =  bool 배열을 사용해서 k 개의 미생물 군집들 중 이미 합쳐진 미생물들은 과정에서 배제한다. (true가 되면 어떤 연산도 적용되지 않도록)

 

* check() -> 파라미터로 받은 좌표에 다수의 미생물 군집이 있는 경우 미생물들의 수는 합쳐지고 가장 미생물을 많이 가지고 있는 군집을 제외하고는 모두 사라진다. 

 

* moveGrups() -> 미생물들을 각 방향에 맞게 움직인다. 

 

* 결과값 : disable[i] 가 false 인 경우 합쳐지지 않고 남아있는 미생물 군집이기 때문에 이 군집들의 미생물 수를 더하면 정답이 된다. 

 

---

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140

#include <iostream> #include <vector> #include <cstring>   using namespace std;   typedef struct Group {     //군집     int x, y, c, d; } G;   int map[101][101]; G groups[1001]; bool disable[1001]; //살아있는지 죽었는지 판단   int n, k, m; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; typedef pair<int, int> pp;   void check(int x, int y) {     //이 좌표 안에 여러개의 군집이 있음           vector<int> expire;     int maxx = 0, maxIdx = 0, sum = 0;     for (int i = 0; i < k; i++)     {         if (disable[i]) continue;         if (groups[i].x == x && groups[i].y == y)         {             if (groups[i].c > maxx)             {                 maxx = groups[i].c;                 maxIdx = i;             }             sum += groups[i].c;             expire.push_back(i);         }     }     for (int i = 0; i < expire.size(); i++)     {         if (expire[i] != maxIdx)         {             disable[expire[i]] = true;         }     }     groups[maxIdx].c = sum; } void moveGroups() {     for (int i = 0; i < k; i++)     {         if (disable[i])             continue;         int x = groups[i].x;         int y = groups[i].y;         int d = groups[i].d;           map[x][y]--; //원래 있던 자리에서 이동함           x += dx[d];         y += dy[d];           groups[i].x = x;         groups[i].y = y;           map[x][y]++;     }       for (int i = 0; i < n; i++) {         for (int j = 0; j < n; j++) {             if (map[i][j] > 1) {                 check(i, j);                 map[i][j] = 1;             }         }     }           for (int i = 0; i < k; i++) {         if (disable[i]) continue;           //약품 처리한 곳에 접근했을 때 처리해줌         int x = groups[i].x;         int y = groups[i].y;         int c = groups[i].c;         int d = groups[i].d;           if (x == 0 || x == n-1 || y == 0 || y == n-1) {             if (groups[i].c == 1) disable[i] = true;             else {                 groups[i].c = c/2;                 groups[i].d = d < 2 ? 1-d : 5-d;             }         }     }       } int main() {       ios_base::sync_with_stdio(0);     cin.tie(0);       int t;     cin >> t;       for (int tc = 1; tc <= t; tc++)     {         cin >> n >> m >> k;         memset(map, 0, sizeof(map));         memset(disable, 0, sizeof(disable));                   int x, y, c, d;         for (int i = 0; i < k; i++)         {             cin >> x >> y >> c >> d;             groups[i].x = x;             groups[i].y = y;             groups[i].c = c;             groups[i].d = d - 1;             map[x][y] = 1;         }           while (m--)         {             //미생물들이 각자의 방향대로 움직인다.             moveGroups();         }         int ans = 0;         for (int i = 0; i < k; i++)         {             if (disable[i])                 continue;             ans += groups[i].c;         }         cout << "#" << tc << " " << ans << '\n';     }     return 0; }