[SWEA] 2382 미생물 격리

2382 미생물 격리

풀이)

백준 17143 낚시왕 문제랑 똑같이 풀었다.

이차원 vector을 사용해서 중복된 위치의 군집을 해결해준다는 것이 핵심이다.

코드)

#include<stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
 
struct virus {
    //세로위치, 가로위치, 미생물 수, 이동방향, 바이러스 구별 인덱스
    int y, x, num, dir, idx;
    virus(int y, int x, int num, int dir,int idx) {
        this->y = y;
        this->x = x;
        this->num = num;
        this->dir = dir;
        this->idx = idx;
    }
};
 
vector <virus> map[100][100];
int dy[5] = { 0,-1,1,0,0 };
int dx[5] = { 0,0,0,-1,1 };
 
bool cmp(const virus &a, const virus &b) {
    return a.num > b.num;
}
 
int main() {
    //freopen("sample_input.txt", "r", stdin);
    int T = 0;
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++) {
        int n, m, k;
        scanf("%d %d %d", &n, &m, &k);
        vector<virus> vi;
        for (int i = 0; i < k; i++) {
            int y, x, n, d;
            scanf("%d %d %d %d", &y, &x, &n, &d);
            vi.push_back({ y,x,n,d,i });
        }
        while (m--)
        {
            //1.미생물이동
            for (int i = 0; i < k; i++) {
                if (vi[i].num == 0) continue;//이미 죽은 군집이면 pass
                vi[i].y += dy[vi[i].dir];
                vi[i].x += dx[vi[i].dir];
                
                if (vi[i].y < 1 || vi[i].y >= n - 1 || vi[i].x < 1 || vi[i].x >= n - 1) {//약품이 칠해진 셀
                    vi[i].num /= 2;//절반이 죽고
                    //방향을 반대로 바꿈
                    if (vi[i].dir == 1 || vi[i].dir == 3) {
                        vi[i].dir += 1;
                    }
                    else {
                        vi[i].dir -= 1;
                    }
                }
                if (vi[i].num > 0) {//미생물의 수가 0보다 많다면
                    map[vi[i].y][vi[i].x].push_back(vi[i]);//지도에 미생물 삽입
                }
        
            }
            //2.미생물의 군집이 2개 이상 모여있을 경우
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (map[i][j].size() > 1) {
                        sort(map[i][j].begin(), map[i][j].end(), cmp);//미생물의 수들로 내림차순
                        virus winner = map[i][j][0];//군집중 가장 미생물 수가 많은 군집
                        for (int t = 1; t < map[i][j].size(); t++) {
                            vi[winner.idx].num += map[i][j][t].num;//미생물수가 가장많은 군집에 합쳐짐
                            vi[map[i][j][t].idx].num = 0;
                        }
                    }
                }
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    map[i][j].clear();
                }
            }
        }
    
        //살아남은 군집의 미생물 수 더하기
        int result = 0;
        for (int i = 0; i < k; i++) {
            if (vi[i].num == 0) continue;
            result += vi[i].num;
        }
        printf("#%d %d\n", test_case, result);
    }
 
    return 0;
}