5653. [모의 SW 역량테스트] 줄기세포배양

[URL]

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo&

SW Expert Academy

 

[풀이 과정]

* 시뮬레이션

 

각 testcase에서

초기화, 입력, 각 시간(K)마다 계산, sum계산

 

(입력)

map[][]입력받는 과정에서 구조체형태로 벡터에 저장

여기서 이후에 방문했는지 확인하기 위해 check[][] = true;

 

(각 시간(K)마다 계산)

벡터의 크기만큼 검사

 

벡터의 상태 체크: 1) 비활성상태 경우 2)활성상태 경우 3) 죽은 경우

벡터.val 계산하여 상태 변경

 

활성상태 경우

 

번식 시작

번식 4방향 탐색 : 가능한가?(isPossible)

 

newCell 벡터에 저장 -> 정렬 후 제일 큰놈빼고 삭제

 

기존 벡터v에 새로생긴 벡터newCell추가

 

sum계산

 

[소스 코드]

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
struct Cell {
    int life;
    int x;
    int y;
    int val;
    int state = 0;        //state: (0)비활성상태, (1)활성상태, (2)죽은상태
};
 
vector <Cell> v;
vector <Cell> newCell;        //새로 번식되서 생긴 Cell 
 
int map[51][51];
// 시간초과해결1. 방문한 곳인지 check배열 설정
bool check[500][500];
 
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
 
bool cmp(Cell A, Cell B) {
    if (A.x == B.x && A.y == B.y)
        return A.life > B.life;
 
    else
    {
        if (A.x == B.x)
            return A.y > B.y;
        else
            return A.x > B.x;
    }
}
 
bool isPossible(int nx, int ny) {
    bool flag = 1;
 
    // 시간초과해결2. 가능한 영역인지 단순히 그곳(nx, ny)로 가서 바로 check한다.
    if (check[250+nx][250+ny] == true)
    {
        flag = 0;
    }
 
    return flag;
}
 
void spread(int cx, int cy, int life) {
    for (int k = 0; k < 4; k++)
    {
        int nx = cx + dx[k];
        int ny = cy + dy[k];
 
        if (isPossible(nx, ny))        // 기존 벡터에 없으면!
        {
            Cell temp;
            temp.x = nx;
            temp.y = ny;
            temp.life = life;
            temp.val = life;
            temp.state = 0;
 
            newCell.push_back(temp);
        }
    }
}
 
int main() {
    int T;
    scanf("%d", &T);
    for (int tc = 0; tc < T; tc++)
    {
        // 초기화 init()
        int sum = 0;
        v.clear();
 
        for (int i = 0; i < 500; i++)
        {
            for (int j = 0; j < 500; j++)
            {
                check[i][j] = 0;
            }
        }
 
        // 입력 input()
        int N, M, K;
        scanf("%d %d %d", &N, &M, &K);
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                scanf("%d", &map[i][j]);
 
                if (map[i][j] != 0)
                {
                    Cell temp;
 
                    temp.life = map[i][j];
                    temp.x = i;
                    temp.y = j;
                    temp.val = map[i][j];
 
                    check[250 + temp.x][250 + temp.y] = true;
                    v.push_back(temp);
                }
            }
        }
 
        // K시간 만큼 계산
        for (int k = 1; k <= K; k++)
        {
            newCell.clear();
 
            for (int i = 0; i < v.size(); i++)
            {
                // (1) 비활성 상태
                if (v[i].state == 0)
                {
                    v[i].val--;
 
                    if (v[i].val == 0)
                    {
                        v[i].state = 1;
                        v[i].val = v[i].life;
                        continue;
                    }
                }
 
                // (2) 활성 상태
                else if (v[i].state == 1)
                {
                    if (v[i].life == v[i].val)
                    {
                        v[i].val--;
 
                        // 번식 시작
                        spread(v[i].x, v[i].y, v[i].life);
 
                        if (v[i].val == 0)
                        {
                            v[i].state = 2;
                        }
                    }
                    else
                    {
                        v[i].val--;
                        if (v[i].val == 0)
                        {
                            v[i].state = 2;
                        }
                    }
                }
 
                // (3) 죽은 상태
                else if (v[i].state == 2)
                {
                    continue;
                }
            }
 
            if (newCell.size() != 0)
            {
                // 새로 생긴 세포 정렬
                sort(newCell.begin(), newCell.end(), cmp);
 
                // 새로 생긴 세포 삭제
                for (int i = 0; i < newCell.size() - 1; )
                {
                    if (newCell[i].x == newCell[i + 1].x && newCell[i].y == newCell[i + 1].y)
                    {
                        newCell.erase(newCell.begin() + i + 1);
                    }
                    else
                    {
                        i++;
                    }
                }
 
                // 새로 생긴 세포 -> 기존 세포벡터에 넣어주기
                for (int i = 0; i < newCell.size(); i++)
                {
                    check[250 + newCell[i].x][250 + newCell[i].y] = true;
                    v.push_back(newCell[i]);
                }
 
            }
            else
                continue;
 
            // 시간초과해결3. 앞에서 계산한 부분은 벡터에서 제외, 이 후 결과에 영향 x
            for (int i = 0; i < v.size() - 1; )
            {
                if (v[i].state == 2)
                {
                    v.erase(v.begin() + i);
                }
                else
                {
                    i++;
                }
            }
        }
 
        for (int i = 0; i < v.size(); i++)
        {
            if (v[i].state != 2)
            {
                sum++;
            }
        }
 
        printf("#%d %d\n", tc + 1, sum);
    }
 
    return 0;
}