[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 인 경우 합쳐지지 않고 남아있는 미생물 군집이기 때문에 이 군집들의 미생물 수를 더하면 정답이 된다. 

 

---

 

#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; }