[SWEA] 5653. 줄기세포배양

5653 줄기세포배양

풀이)

처음에는 어떻게 좌표를 잡아야하는지 몰라서, 

set을 이용해서 이미 세포가 있는 곳은 번식하지 않게 했다.

(세포는 struct sepo{}를 선언해서 관련 정보를 저장했고)

그러다보니 통과는 했지만 시간이 어마 무시했다.

set을 이용한 코드)

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <set>
using namespace std;
 
set <pair<int, int>>visited;
 
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
struct sepo {
    int y, x;
    int life; //생명력
    int time;
    bool active;
 
    sepo(int y, int x,int time, bool active) {
        this->y = y;
        this->x = x;
        this->life = time;
        this->time = time;
        this->active = active;
    }
 
};
 
bool cmp(const sepo &a, const sepo &b) {
    if (a.y == b.y && a.x == b.x) {
        return a.life > b.life;
    }
    if (a.x == b.x) {
        return a.y < b.y;
    }
    else {
        return a.x < b.x;
    }
}
 
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<sepo> se;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int temp;
                scanf("%d", &temp);
                if (temp > 0) {
                    se.push_back({ i,j,temp,false });
                    visited.insert({ i,j });
                }
            }
        }
        vector <sepo> temp;
        while (k--)
        {
            
            for (int i = 0; i < se.size(); i++) {
                if (se[i].time == 0 && se[i].active==false)continue;
                
                if (se[i].active) {
                    if (se[i].life == se[i].time) {//맨처음 1시간
                        //번식일어남
                        for (int j = 0; j < 4; j++) {
                            int ny = se[i].y + dy[j];
                            int nx = se[i].x + dx[j];
                            if (visited.find({ ny,nx }) != visited.end())continue;//이미 하나의 줄기세포 존재
                            temp.push_back({ ny,nx,se[i].life,false });
                        }
                    }
                    se[i].time -= 1;
                    if (se[i].time == 0) {
                        se[i].active = false;//완전히 죽음
                    }
                    continue;
                }
                se[i].time -= 1;
                if (se[i].time == 0 && se[i].active == false) {
                    se[i].active = true; //활성화
                    se[i].time = se[i].life;
                    continue;
                }
                
            }
            if (temp.empty())continue;
            //예비번식자 중 하나의 그리드 셀에 동시 번식하려면 빼줌
            sort(temp.begin(), temp.end(), cmp); // 생명력내림차순
            for (int i = 0; i < temp.size(); i++) {
                if (visited.find({temp[i].y,temp[i].x}) != visited.end())continue;
                visited.insert({ temp[i].y,temp[i].x });
                se.push_back(temp[i]);
            }
            temp.clear();
        }
        int result = 0;
        for (int i = 0; i < se.size(); i++) {
            if (se[i].time >0) result++;
        
        }
        printf("#%d %d\n", test_case, result);
        visited.clear();
    }
    return 0;
}

시간을 어떻게 줄이는 지 싶어 다른 분의 코드를 보니,

왜 이 생각을 못했나 싶었다.

"줄기 세포의 수명은 1~10년, 그리드는 1~50, 시간은 최대 300 이니깐

 최악의 경우를 생각했을 때

 수명이 1인 줄기 세포가 50*50 그리드를 꽉 채우고 있을 때인데

 그래봤자 2시간당 1칸밖에 안움직이니깐 최대로 가봤자 상하좌우 150칸이내이다"

이 생각을 적용해서 이미 세포가 있음을 표시하는 visited를 이제는 set이 아니라

배열로 선언해서 풀었다.

그러니 시간이 2배넘게 절약되었다.

배열을 이용한 코드)

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <set>
using namespace std;
 
#define BASE 200
 
int visited[500][500];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
struct sepo {
    int y, x;
    int life;
    int time;
    bool active;
 
    sepo(int y, int x,int time, bool active) {
        this->y = y;
        this->x = x;
        this->life = time;
        this->time = time;
        this->active = active;
    }
 
};
 
bool cmp(const sepo &a, const sepo &b) {
    if (a.y == b.y && a.x == b.x) {
        return a.life > b.life;
    }
    if (a.x == b.x) {
        return a.y < b.y;
    }
    else {
        return a.x < b.x;
    }
}
 
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<sepo> se;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int temp;
                scanf("%d", &temp);
                if (temp > 0) {
                    se.push_back({ i+BASE,j+BASE,temp,false });
                    visited[i + BASE][j + BASE] = true;
                }
            }
        }
        vector <sepo> temp;
        while (k--)
        {
            
            for (int i = 0; i < se.size(); i++) {
                if (se[i].time == 0 && se[i].active==false)continue;//이미 번식끝난아이
                
                if (se[i].active) {
                    if (se[i].life == se[i].time) {
                        //번식일어남
                        for (int j = 0; j < 4; j++) {
                            int ny = se[i].y + dy[j];
                            int nx = se[i].x + dx[j];
                            if (visited[ny][nx])continue;//이미 하나의 줄기세포 존재
                            temp.push_back({ ny,nx,se[i].life,false });
                        }
                    }
                    se[i].time -= 1;
                    if (se[i].time == 0) {
                        se[i].active = false;//완전히 죽음
                    }
                    continue;
                }
                se[i].time -= 1;
                if (se[i].time == 0 && se[i].active == false) {
                    se[i].active = true; //활성화
                    se[i].time = se[i].life;
                    continue;
                }
                
            }
            if (temp.empty())continue;
            //예비번식자 중 하나의 그리드 셀에 동시 번식하려면 빼줌
            sort(temp.begin(), temp.end(), cmp);
            for (int i = 0; i < temp.size(); i++) {
                if (visited[temp[i].y][temp[i].x])continue;
                visited[temp[i].y][temp[i].x] = true;
                se.push_back(temp[i]);
            }
            temp.clear();
        }
        int result = 0;
        for (int i = 0; i < se.size(); i++) {
            if (se[i].time >0) result++;
        
        }
        printf("#%d %d\n", test_case, result);
        memset(visited, false, sizeof(visited));
    }
    return 0;
}

+이거 말고도 다른 방법을 사용하신 분이 없나 싶어 살피니깐

queue를 배열로 선언해서 푸신 분도 있었다.

세포가 번식할 때, 생명력 수치가 높은 세포가 우선순위를 갖는데

이를 이용해서 queue를 생명력 순으로 나눴다.

queue<pair<int, int> > q[11]; 로 선언해, 

생명력이 10인 줄기세포부터 번식 즉 q[10]에 들은 세포부터 

번식시켜서 visited를 true로 바꿔놓는 방법이었다.