[SWEA] 미생물 격리

[SWEA] 미생물 격리

Problem URL : 미생물 격리

# include <iostream>
# include <cstring>
# include <vector>
# include <algorithm>

using namespace std;

int n, m, k;
int map[100][100];
int dir[5][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };

struct Community {
    int x;
    int y;
    int number;
    int originalNumber;
    int dir;
    Community(int _y, int _x, int _number, int _dir) : y(_y), x(_x), number(_number), dir(_dir) {};
};

vector <Community> community;

bool inChemical(int ny, int nx) {
    if (ny == 0 || ny == n - 1 || nx == 0 || nx == n - 1) {
        return true;
    }
    return false;
}

// 최종 미생물 수 합 반환
int result() {
    int result = 0;
    for (int j = 0; j < community.size(); j++) {
        result += community[j].number;
    }
    return result;
}

int solution() {
    for (int i = 0; i < m; i++) {
        memset(map, -1, sizeof(map));
        for(int index = 0; index < community.size(); index++){
            // 미생물이 없는 군집은 PASS
            if (community[index].number == 0) {
                continue;
            }

            community[index].originalNumber = community[index].number;
            int ny = community[index].y + dir[community[index].dir][0];
            int nx = community[index].x + dir[community[index].dir][1];
            community[index].y = ny;
            community[index].x = nx;
            int mapIndex = map[ny][nx];
            map[ny][nx] = index;

            if (mapIndex >= 0) {
                if (community[index].originalNumber > community[mapIndex].originalNumber) {
                    // 움직여간 군집이 기존 자리(ny, nx)에 있던 군집보다 미생물 수가 큰 경우
                    community[index].number += community[mapIndex].number;
                    community[mapIndex].number = 0;
                } else {
                    // 움직여간 군집이 기존 자리(ny, nx)에 있던 군집보다 미생물 수가 작은 경우
                    community[mapIndex].number += community[index].number;
                    community[index].number = 0;
                    map[ny][nx] = mapIndex;
                }
            } else if (inChemical(ny,nx)) {
                // 군집이 약품(가장자리)에 이동한 경우
                community[index].number /= 2;
                if (community[index].number == 0) {
                    map[ny][nx] = -1;
                }
                community[index].dir = (5-community[index].dir)%4;
            }
        }
    }

    return result();
}

int main() {
    int TC;
    cin >> TC;

    for (int tc = 1; tc <= TC; tc++) {
        cin >> n >> m >> k;
        memset(map, -1, sizeof(map));
        community.clear();

        int y, x, number, dir;

        for (int i = 0; i < k; i++) {
            cin >> y >> x >> number >> dir;
            community.push_back(Community(y, x, number, dir-1));
        }
        cout << "#" << tc << " " << solution() << endl;
    }

    return 0;
}