[ SWEA 5653 ] 줄기세포배양 (C++)

SWExpertAcademy 줄기세포배양(5653) 문제이다.

[ 문제풀이 ]

1) 굉장히 까다로운 문제였다. 지금부터 천천히 같이 해결해보도록 하자.

   본인의 풀이법은 모든 값들을 미리 세팅해놓는 방법이다. 줄기세포를 나타내는 구조체를 하나 만들어서 사용해주었다.

   그 구조체 안에는 다음과 같은 변수들이 들어가있다.

   { x좌표 , y좌표 , 만들어진시간 , 생명력수치 , 활성화시간 , 죽는시간 , 상태 }

   위에서 말했듯이 이 구조체 벡터를 하나 만들어서 모든 줄기세포들에 대한 정보를 다 세팅하고 처리해주었다.

   위의 변수들의 쓸모부터 알아보자.

   가장 먼저 x좌표 y좌표이다. 이 값에는 현재 줄기세포의 (x, y) 값이 저장되게 된다. 또한, 이 값들을 통해서 우리는 MAP에

   줄기세포를 표시하게 된다.

   두 번째는 만들어진 시간이다. 이게 왜 필요할까?? 바로 이 뒤에서 설명할 '활성화시간'에 영향을 미치는 놈이기 때문이다.

   왜 영향을 미칠까??

   예를 들어서 초기상태에 존재하는 생명력수치가 2인 줄기세포가 있다고 가정해보자.

   이 줄기세포의 만들어진 시간 = 0초일 것이고, 활성화되는 시간은 2초일 것이다.

   그렇다면 이 줄기세포가 번식한 줄기세포들의 활성화 시간은 몇초일까 ??? 5초이다.

   5초가 나오게 된 이유는 2초에서 활성화되고, 3초에 만들어질 것이고, 3초에서 2초동안 기다린 후에 5초에 활성화 되고 번식을

   하게 될 것이다. 이 계산을 해주기 위해서 만들어진 시간을 넣어주었다.

   만들어진 시간을 넣어서 계산해본다면, 2초에 활성화되는 줄기세포의 의해서 번식되는 줄기세포는 '3'초에 만들어질 것이다.

   (2초에 활성화되고 1초동안 번식을 하기 때문에 !)

   그리고 활성화되는 시간은 '3'초에 2초를 더한 5초가 될 것이다. 이 계산을 위해 본인은 만들어진 시간 또한 구조체에 넣어

   주었다.

   세번째는 생명력 수치이다. 이건 뭐 당연히 필요한 것이기 때문에 !

   네번째는 활성화시간이다. 우리는 이 계산을 위해서 위에서 만들어진 시간을 계산해 놓았다.

   즉, 활성화시간 = 만들어진 시간 + 생명력 수치가 된다.

   다섯번째는 죽는시간이다. 죽는 줄기세포들에 의해서는 번식이 이루어지지 않는다. 또한 이 값에 의해서 이 다음에 말할

   줄기세포의 '상태'가 결정되어진다. 그렇다면 죽는 시간을 계산해보자.

   0초에 만들어진 생명력수치가 2인 줄기세포는 2초에 활성화 되고 4초에 죽게된다.

   3초에 만들어진 생명력수치가 2인 줄기세포는 5초에 활성화 되고 7초에 죽게된다.

   즉, 죽는시간은 = 활성화시간 + 생명력수치 가 된다.

   마지막은 상태를 나타내는 bool형 변수이다. 죽는시간이 되면 상태를 false로, 그게 아닌 활성화 혹은 비활성화 시간일 때에는

   true의 값으로 표현해 주었다.

2) 시작부터 뭐 문제 풀이의 핵심을 말해버렸다. 이제는 다시 처음으로 돌아가서 입력받는 부분부터 생각해보자.

   문제에 이런 조건이 있다. "줄기세포가 배양 용기 가장자리에 닿아서 번식할 수 없는 경우는 없다..."

   즉, 어떤 경우에도 맵의 범위가 아니라서 번식할 수 없는 경우는 없다는 말이다. 문제를 정말 대충 읽었다면 맵 크기 최대 50

   이잖아! 라고 말할 수 있지만 사실은 그게 아니다.

   문제의 조건을 다시한번 읽어보자.

   1. 초기상태에 줄기세포가 분포된 영역의 최소 (1,1)에서 최대 (50, 50)이다.

   2. 배양시간은 최소 1시간에서 최대 300시간이다.

   3. 줄기세포가 가장자리에 닿아서 번식할 수 없는 경우는 없다.

   즉 ! 우리는 맵의 크기 조차 우리가 생각해내서 구현해줘야 한다.

   맵의 최대사이즈를 구해보자. 0초에 (50, 50)에 있는 생명력수치가 1인 놈이 있다고 생각해보자.

   아마 이 친구는 1초에 활성화되고 2초에 번식을할 것이다.

   즉, 2초에 (50, 51)에 줄기세포가 하나 더 생길것이다.(문제에서는 4방향이지만 간단한 설명을 위해서 오른쪽으로 번식하는

   경우만 설명하겠습니다)

   이 친구는 3초에 활성화되고 4초에 (50, 52)에 번식을 할 것이다.

   즉, 2초당 한칸씩 더 번식을 하는 꼴이다. 2초에 1칸증가, 4초에 2칸증가, 6초에 3칸증가 .....

   그렇다면 300초가 지나면 어떻게될까?? 300초에는 150칸이 증가할 것이다. 즉, (50, 200)에 번식을 할 것이다.

   아하 ! 그렇다면 맵의 최댓값을 150으로 잡으면 될까 ??? 잘 생각해보자. 이제는 4방향 모두 계산을 해보겠다.

   (50, 50)에 의해서 300초가 지나게 되면 오른쪽으로는 (50, 200)에 번식하고, 왼쪽으로는 (50, -100)에 번식하고

   북쪽으로는 (-100, 50)에 번식하고 남쪽에는 (150, 50)에 증가하게 될 것이다.

   맵의 최댓값을 150으로 잡게 되면 -100이 라는 문제점이 생기게 된다.

   이거는 그나마 (50, 50)이라서 그렇지 (0, 0)에 입력받았다고 생각해보자. 아마 (-150, 0), (150, 0), (0, 150), (0, -150)에 번식을

   하게 될 것이다. 그렇다면 이 음수를 없애기 위해서 어떻게 해줘야할까??

   초기에 입력받는 좌표 + 150을 해줘버리면된다. 즉 (0, 0)을 입력받는다면 (150, 150)에 입력을 받게 되는것이다.

   여기서 하나를 더 생각해야한다. 우리가 처음에 알아낸 것이 무엇일까?? 번식시간의 최대인 300초에는 150칸이 증가한다.

   즉, (150, 150) 에서 150칸이 증가하는 경우의 최대의 경우이다. 즉 (150, 300) 이런식으로 최대 좌표가 300이 나오는 경우가

   발생한다.

   따라서 우리는 ! 맵의 전체크기를 300x300 으로 잡은 후에, 입력받는 좌표의 크기를 + 150씩 해주면 그 때서야

   "줄기세포가 맵의 가장자리에 닿아서 번식을 못하는 경우는 없다" 를 만족시킬 수 있다.

3) 마지막으로 줄기세포들의 관리와 번식시킬 때 유의점만 설명하고 마치겠다.

   본인은 줄기세포들을 모두 Vector에 넣어서 관리해주었다. 새로운 줄기세포들이 번식할 때도 마찬가지이다.

   하지만, 번식시킬 때 이런 문제점이 있다. 동시에 같은 곳에 번식하려는 경우에는 생명력 수치가 더 높은 놈이 우선순위를 갖는

   다. 본인은 이 부분을 위해서 먼저 임시적인 Vector를 하나 만들어주어서 "번식되는 줄기세포들의 정보" 를 저장해주었다.

  

   즉 위의 그림에서 파랑색 동그라미 친 놈들의 정보들을 임시적인 Vector에 모두 저장해준다.

   이 후, 그 Vector를 생명력 수치에 따라서 정렬시켜주었다. 생명력 수치가 높은 친구들일수록 앞으로 오도록

   이 후 번식을 시작하면된다. 그렇게 되면 같은 좌표를 여러번 방문할 경우에는, 이미 방문한 줄기세포의 생명력 수치가 더 높다

   는 의미일 것이고, 그 경우에는 보다 생명력수치가 낮은 줄기세포들이 번식을 하는 것을 막을 수가 있다.

   사실 이렇게 하면 시간이 조금 오래걸리기는 한다.. 그런데 보다 특별한 방법이 떠오르질 않아 본인은 이렇게 군현해 보았다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
 
#define endl "\n"
#define MAX 350
#define SIZE 150
using namespace std;
 
typedef struct
{
    int x;
    int y;
    int Born_Time;
    int Life_Value;
    int Die_Time;
    int Active_Time;
    bool State;    
}Cell;
 
int N, M, K;
int Answer;
int MAP[MAX][MAX];
vector<Cell> V;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Initialize()
{
    memset(MAP, 0, sizeof(MAP));
    V.clear();
    Answer = 0;
}
 
bool Standard(Cell A, Cell B)
{
    if (A.Life_Value > B.Life_Value) return true;
    return false;
}
 
void Input()
{
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            int a; cin >> a;
            if (a == 0) continue;
            MAP[i + SIZE][j + SIZE] = a;
 
            Cell Temp;
            Temp.x = i + SIZE;
            Temp.y = j + SIZE;
            Temp.State = true;
            Temp.Life_Value = a;
            Temp.Born_Time = 0;
            Temp.Active_Time = Temp.Born_Time + Temp.Life_Value;
            Temp.Die_Time = Temp.Active_Time * 2;
            V.push_back(Temp);
        }
    }
}
 
void Print()
{
    bool Visit[MAX][MAX];
    memset(Visit, true, sizeof(Visit));
    for (int i = 0; i < V.size(); i++)
    {
        int x = V[i].x;
        int y = V[i].y;
        if (V[i].State == false)
        {
            Visit[x][y] = false;
        }
    }
    cout << "####################################" << endl;
    for (int i = 140; i < 165; i++)
    {
        for (int j = 140; j < 165; j++)
        {
            if (Visit[i][j] == false) cout << "- ";
            else cout << MAP[i][j] << " ";
        }
        cout << endl;
    }
    cout << "####################################" << endl;
 
}
 
void Do_Die(int T)
{
    for (int i = 0; i < V.size(); i++)
    {
        if (V[i].Die_Time == T)
        {
            V[i].State = false;
        }
    }
}
 
void Do_Active(int T)
{
    vector<Cell> V_Temp;
    for (int i = 0; i < V.size(); i++)
    {
        if (V[i].State == false) continue;
        if (V[i].Active_Time == T)
        {
            int x = V[i].x;
            int y = V[i].y;
            int Lv = V[i].Life_Value;
 
            for (int j = 0; j < 4; j++)
            {
                int nx = x + dx[j];
                int ny = y + dy[j];
 
                if (MAP[nx][ny] != 0) continue;
 
                Cell Temp;
                Temp.x = nx;
                Temp.y = ny;
                Temp.Life_Value = Lv;
                Temp.State = true;
                Temp.Born_Time = T + 1;
                Temp.Active_Time = Temp.Born_Time + Temp.Life_Value;
                Temp.Die_Time = Temp.Active_Time + Temp.Life_Value;
                
                V_Temp.push_back(Temp);
            }
        }
    }
 
    if (V_Temp.size() == 0) return;
    sort(V_Temp.begin(), V_Temp.end(), Standard);
 
    for (int i = 0; i < V_Temp.size(); i++)
    {
        int x = V_Temp[i].x;
        int y = V_Temp[i].y;
        int Lv = V_Temp[i].Life_Value;
 
        if (MAP[x][y] != 0) continue;
        MAP[x][y] = Lv;
        V.push_back(V_Temp[i]);
    }
}
 
void Solution() 
{
    int Time = 0;
    while (1)
    {
        if (Time == K) break;
        Do_Die(Time);
        Do_Active(Time);
        Time++;
    }
 
    int No_Count = 0;
    for (int i = 0; i < V.size(); i++)
    {
        if (V[i].State == false) No_Count++;
        if (V[i].Die_Time == K) No_Count++;
        if (V[i].Born_Time == K + 1) No_Count++;
    }
 
    Answer = V.size() - No_Count;
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}