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

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

SW Expert Academy

이 문제에서 어려운 부분은두 개 이상의 군집이 하나의 셀에 모이는 경우인 것 같다.

어떻게 처리를 해줘야하나 한참 고민을 했었고, 처음엔 틀렸었다...ㅎ

 

이 부분을 처리해주기 위해서 먼저 군집들의 정보를 저장하기 위해 구조체를 만들어줬다.

군집 정보에는 x, y 좌표, 미생물 수(cnt), 방향(dit), 그리고 추가적으로 미생물 수 합을 저장하는 변수 sum을 만들었다.

그리고 배열을 만들어서 배열의 x, y좌표에는 해당 위치에 있는 군집의 번호를 기록해줬다.

매시간마다 위치는 바뀌기 때문에 배열의 값도 바뀌어야 하는데 그냥 헷갈지않게 배열 전체를 -1로 초기화해버렸다.

 

이동할 위치의 값이 -1(초기값)인 경우에는 아무 군집도 존재하지 않으므로 바로 그 위치로 이동한다.

그렇지 않은 경우에는, 기록되어 있는 인덱스를 이용해서 해당 위치에 있는 군집의 미생물 수와 현재 군집의 미생물 수를 비교해준다.

 

현재 미생물 수(cnt)가 더 큰 경우에는 배열의 값을 현재 군집의 번호로 바꿔주고 이전 군집의 미생물 수의 합(sum의 값)을 현재 미생물 수의 합에 더해준다. 그리고 이전 군집의 cnt와 sum은 0으로 만들어줌으로써 없애준다. 반대의 경우에도 비슷한 방식으로 처리해준다.

 

sum 변수를 추가적으로 써주는 이유는 3개이상의 군집이 하나의 셀에 모일 수 있기 때문이다.

위와 같은 상황에서 또 다른 군집이 같은 위치에 왔을 때, 이미 있는 군집의 cnt와 비교를 해줘야 하기 때문이다

즉, 합쳐진 값인 sum과 비교를 하면 안된다. 그리고 다시 새로 온 군집의 cnt가 더 큰 경우에는 이전 군집의 sum(앞에서 합쳐진 두 개의 군집의 미생물수)를 현재 군집의 sum에 더해주고, 이전 군집의 cnt와 sum은 다시 0으로 만들어준다.

 

 

이런 식으로 현재시간에 군집들의 이동이 모두 끝났다면

미생물 수(cnt)를 합쳐진 값(sum)으로 바꿔주면 된다.

그리고 이제 사라진 애들은 이동할 필요가 없기 때문에 cnt가 0인 애들은 continue 해준다

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
int ans;
int n, m, k;
 
int dx[] = { 0,-1,1,0,0 };
int dy[] = { 0,0,0,-1,1 };
int map[100][100];
 
struct Group {
    int x;
    int y;
    int cnt;
    int dir;
    int sum;
    Group(int x, int y, int cnt, int dir, int sum) : x(x), y(y), cnt(cnt), dir(dir), sum(sum) {}
};
 
vector<Group> vt;
 
 
void solve() {
    
    int time = 0;
 
    //m시간 동안 진행
    while (time++ < m) {
        memset(map, -1, sizeof(map));
 
        //모든 군집 이동
        int x, y, cnt, dir;
        for (int i = 0; i < k; i++) {
            //사라진 군집은 이동하지 않는다.
            if (vt[i].cnt == 0) continue;
 
            //일단 값들 변수에 꺼내놓는다.
            x = vt[i].x;
            y = vt[i].y;
            cnt = vt[i].cnt;
            dir = vt[i].dir;
 
            //이동
            x += dx[dir];
            y += dy[dir];
 
 
            //이동한 좌표 새로 저장
            vt[i].x = x;
            vt[i].y = y;
 
 
            //약품이 칠해진 구역이면 미생물 수 반으로 감소 후 방향 반대로 전환
            if (x == 0 || y == 0 || x == n - 1 || y == n - 1) {
                vt[i].cnt /= 2;
                vt[i].sum /= 2;
                if (dir == 1 || dir == 3) {
                    vt[i].dir += 1;
                }
                else {
                    vt[i].dir -= 1;
                }
            }
            else {
                //약품이 칠해지지 않은 구역인 경우
                //이동한 곳에 아무도 없으면 현재 군집 번호를 저장
                if (map[x][y] == -1) {
                    map[x][y] = i;
                }
                else {
                    //이동한 곳에 이미 다른 군집이 있다
 
                    //이미 있는 군집의 미생물 수가 더 큰 경우
                    if (cnt < vt[map[x][y]].cnt) {
                        //현재 군집의 미생물 수의 합을 합쳐주고
                        vt[map[x][y]].sum += vt[i].sum;
 
                        //현재 군집은 없애준다.
                        vt[i].cnt = 0;
                        vt[i].sum = 0;
                    }
                    else {
                        //현재 군집의 미생물 수가 더 큰 경우
 
                        //이전 군집의 미생물 수 합을 현재 군집의 합에 더해주고
                        vt[i].sum += vt[map[x][y]].sum;
 
                        //이전 군집은 없애준다.
                        vt[map[x][y]].cnt = 0;
                        vt[map[x][y]].sum = 0;
 
                        //현재 군집의 번호를 새로 저장해준다.
                        map[x][y] = i;
                    }
 
                }
 
            }
 
 
 
        }
 
 
        //모든 군집의 이동이 끝났으면 합쳐진 미생물의 합을 군집의 미생물 개수로 바꿔준다.
        for (int i = 0; i < k; i++) {
            vt[i].cnt = vt[i].sum;
        }
 
    }
 
    //남은 미생물의 수를 세준다.
    for (int i = 0; i < k; i++) {
        ans += vt[i].cnt;
    }
 
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        ans = 0;
        vt.clear();
 
        cin >> n >> m >> k;
 
        int x, y, cnt, dir;
        for (int i = 0; i < k; i++) {
            cin >> x >> y >> cnt >> dir;
            vt.push_back(Group(x, y, cnt, dir, cnt));
        }
 
        solve();
 
        cout << '#' << tc << ' ' << ans << '\n';
    }
 
 
    return 0;
}