ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [SWEA] 2382 미생물 격리
    문제 풀이 2020. 5. 7. 20:50

    2382 미생물 격리


    풀이)

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


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


    코드)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    #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;
            this->= 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 == 0continue;//이미 죽은 군집이면 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 == 0continue;
                result += vi[i].num;
            }
            printf("#%d %d\n", test_case, result);
        }
     
        return 0;
    }
    cs


    '문제 풀이' 카테고리의 다른 글

    [SWEA] 1952. 수영장  (0) 2020.05.08
    [SWEA] 1953 탈주범 검거  (0) 2020.05.08
    [SWEA] 2477 차량 정비소  (0) 2020.05.06
    [SWEA] 2112. 보호필름  (0) 2020.05.04
    [SWEA]2105 디저트 까페  (0) 2020.05.01

    댓글

Designed by Tistory.