ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 5653.줄기세포배양
    알고리즘/SW Expert Academy 2020. 6. 6. 16:40

    이번에 풀어볼 문제는 SW Expert의 줄기세포 배양이다.

     

    SW Expert Academy

    SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

    swexpertacademy.com

    이 문제에서는 배울게 정말 많았던거 같다. 내용은 그렇게 어렵지않다. 그냥 문제에서 시키는대로 하면된다.

    문제는 그 설계가 생각보다 복잡하다는 것이다. 

    결국 다른사람의 코드를 보고 이해하면서 배우는 선택을 했다.. 후..;; ( 참고 : https://it-earth.tistory.com/51 )

    이 분의 풀이법을 보면 굉장히 체계적으로 딱딱 맞아떨어진다고 생각한다.

    vector를 구조체를 이용해서 정확하게 문제에서 필요한 요구조건들을 확인해간다.

    무엇보다 탐색기준을 시간을 잡는 건 생각을 못했던거 같다... 그래도 배웠으니까 긍정적으로 생각해야겠다.

     


     

    < Code 설명 >

    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
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    #pragma warning(disable:4996)
     
    #include <iostream>
    #include <vector>
     
    #define MAX 400
     
    using namespace std;
     
    int T, N, M, K;
    struct cell{
        int x;
        int y;
        int life;
        int flow;
        int status;
        bool work;
    };
     
    vector<cell>cells, birth, alive;
    int maxlife[MAX][MAX];
    int status[MAX][MAX]; // 1:비활 2:활 3:다이
    int dx[4= { 001-1 };
    int dy[4= { 1-100 };
     
    void reset(){ //사용 배열 초기화
        for (int i = 0; i < MAX; i++){
            for (int j = 0; j < MAX; j++){
                maxlife[i][j] = status[i][j] = 0;
            }
        }
    }
    int search(){
        for (int time = 1; time <= K; time++){ // 시간을 기준으로 진행
            for (int i = 0; i < cells.size(); i++){ // 배양한 세포의 좌표만을 이용하기위해 size
                if (cells[i].status != 3){    // 죽은세포가 아니라면
                    if (cells[i].status == 1){// 그중 비활성화된 세포면
                        if (time == cells[i].flow){ // 이세포가 시간에 흐름에 따라 생명과 같아지면
                            cells[i].status = 2;  // 상태를 활성화로 바꿔주고
                            status[cells[i].x][cells[i].y] = 2// 상태 배열도 활성화로 나타내준다.
                            cells[i].flow = time + cells[i].life; // 생명력만큼 시간이 흘렀고 그 시간을 활성화한 이후부터 더해주어야 생명력만큼 활성화할 수 있다.
                        }
                    }
                    else if (cells[i].status == 2){ // 활성화된 세포라면
                        if (cells[i].work==true){  // 번식이 가능한지 확인하고 가능하다면
                            for (int z = 0; z < 4; z++){ // 퍼진다.
                                int ax = cells[i].x + dx[z];
                                int ay = cells[i].y + dy[z];
                                if (status[ax][ay] == 0){ //주변에 배양공간이 있는것이 발견된다면
                                    if (maxlife[ax][ay] < cells[i].life){ // 그 공간에 발견된 곳이 최대생명력보다 배양할 세포의 생명력이 크다면
                                        birth.push_back({ ax, ay, cells[i].life, time + cells[i].life, 1true }); // 새로운 새포 배양
                                        status[ax][ay] = 1// 상태를 비활성화로 배양
                                        maxlife[ax][ay] = cells[i].life; // 최대크기의값을 갱신
                                    }
                                }
                            }
                            cells[i].work = false// 배양이 끝났으므로 기존세포는 1시간만 배양가능하기 때문에 번식력을 잃음
                        }
                        if (time == cells[i].flow){ // 활성화상태가 된 이후로 진행한시간이 생명력과 같아지면 세포는 죽음
                            status[cells[i].x][cells[i].y] = 3// 죽은 세포 표시
                            cells[i].status = 3// 해당 세포의 상태도 죽음으로 표시
                        }
                    }
                }
            }
            for (int t = 0; t < cells.size(); t++){ 
                if (cells[t].status != 3){ // 죽은 세포들이 아닌 것들은
                    alive.push_back(cells[t]); // 살아있는 세포에 저장
                }
            }
            cells.clear(); // 세포상태를 비움
            for (int t = 0; t < birth.size(); t++){ // 새로태어난 세포들중에
                alive.push_back(birth[t]); // 살아있는 세포에 저장
            }
            for (int t = 0; t < alive.size(); t++){ // 살아있는 세포들을 모아서
                cells.push_back(alive[t]); // 탐색을위해 저장
            }
            alive.clear(); // 살아있는세포들을 다음 탐색을 위해 비움
            birth.clear(); // 새로태어난 새포들도 다음 탐색을 위해 비움
        }
        return (int)cells.size(); // 마지막에 있는 죽은세포외의 모든 세포들 리턴
    }
     
    int main() {
        freopen("5653.txt""r", stdin);
        cin >> T;
        for (int z = 1; z <= T; z++){
            reset(); //새로운 테스트케이스를 위한 초기화
            cells.clear(); // 세포정보도 초기화
            cin >> N >> M >> K;
            int life;
            for (int i = 0; i < N; i++){
                for (int j = 0; j < M; j++){
                    cin >> life;
                    if (life){
                        cells.push_back({ i + 150, j + 150, life, life, 1true }); //최대300이므로 150정도로 잡음
                        status[150 + i][150 + j] = 1// 해당 값의 시작점들은 비활성상태로 시작
                    }
                }
            }
            cout << "#" << z << " " << search() << "\n"// 탐색진행
        }
        return 0;
    }
    cs

    '알고리즘 > SW Expert Academy' 카테고리의 다른 글

    5656.벽돌깨기  (0) 2020.06.12
    2117.홈 방범 서비스  (0) 2020.06.06
    5653.줄기세포배양  (0) 2020.06.06
    1949.등산로 조성  (0) 2020.06.03
    5644.무선충전  (0) 2020.06.02
    1229.암호문2  (0) 2020.03.31

    댓글 0

Designed by Tistory.