[SW Expert Academy] 미생물 격리_2382

군집 내에 방향, 위치, 크기같은 정보들이 필요했기 때문에 구조체를 사용했다. 

이미 군집이 있던 위치로 간 경우, 군집들의 크기를 서로 비교하기 위해서 maxSize라는 변수를 사용했다. 

자신의 군집의 크기가 가장 큰 경우, 방향과 maxSize를 자신의 방향과 사이즈로 바꾼다. 

(num은 합쳐진 군집들의 크기고 maxSize는 군집들 여러개중에 가장 큰 군집의 크기이다.)

 

* 실수했던 것 *

isOut 체크를 군집의 크기를 나타내는 N이 아니라 n으로 검사했다. 

#include <iostream>
#include <string.h>
#include <cmath>
using namespace std;
 
struct bug {
    int num = 0; // 각 군집 내 미생물 수
    int dir = 0; // (상: 1, 하: 2, 좌: 3, 우: 4)
    int maxSize = 0; //군집이 합쳐지기전 가장 큰 군집의 크기 
};
 
int direction[5][2] = { {0,0},{-1,0},{1,0},{0,-1},{0,1} }; //상, 하, 좌, 우
int T, N, M, K; 
int y, x, n, d;
struct bug area[100][100];
struct bug newArea[100][100];
 
bool isOut(int y, int x) {
    return x == 0 || x == N - 1 || y == 0 || y == N - 1;
}
int reverseDir(int dir) {
    if (dir == 1 || dir == 2) return (3 - dir);
    else return (7 - dir);
}
 
void bfs(int y, int x) {
    int d = area[y][x].dir;
    int size = area[y][x].num;
    int ny = y + direction[d][0];
    int nx = x + direction[d][1];
    //약품이 칠해진 셀에 도착한 경우
    if (isOut(ny, nx)) {
        int res = floor(size / 2);
        newArea[ny][nx].num = res;
        newArea[ny][nx].dir = reverseDir(d);
        newArea[ny][nx].maxSize = res;
    }
    else if (newArea[ny][nx].num) { //이미 군집이 있는 위치
        if (newArea[ny][nx].maxSize < size) {
            newArea[ny][nx].maxSize = size;
            newArea[ny][nx].dir = d;
        }
        newArea[ny][nx].num += size;
    }
    else if (!newArea[ny][nx].num) { //아무것도 없는 위치로 간 경우 
        newArea[ny][nx].num = size; 
        newArea[ny][nx].dir = d;
        newArea[ny][nx].maxSize = size;
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> N >> M >> K; 
        memset(area, 0, sizeof(area));
        for (int j = 0; j < K; j++) {
            cin >> y >> x >> n >> d; 
            area[y][x].num = n;
            area[y][x].dir = d;
        }
        while (M--) {
            memset(newArea, 0, sizeof(newArea));
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    if (area[j][k].num) bfs(j, k);
                }
            }
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    area[j][k] = newArea[j][k];
                }
            }
        }
        int sum = 0;
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                sum += area[j][k].num;
            }
        }
        cout << "#" << i + 1 << " " << sum << endl;
    }
    return 0;
}