[SWEA 5653] 줄기세포 배양

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

SW Expert Academy

#include <cstdio>
#include <cstring>
#include <queue>
int T;
int N, M;
int K;
int in[300 + 2][300 + 2];
int board[1000 + 2][1000 + 2];
 
struct _st
{
    int r, c;   // 좌표
    int X;      // 생명력
    int t;      // 언제 해당 상태가 되었는지
};
 
struct NCOMP
{
    bool operator()(const _st &a, const _st &b)
    {
        return a.t + a.X > b.t + b.X;
    }
};
 
 
struct COMP
{
    bool operator()(const _st &a, const _st &b)
    {
        if (a.t == b.t) return a.X < b.X;
        return a.t > b.t;
    }
};
 
std::priority_queue<_st, std::vector<_st>, NCOMP> nonAC;
std::priority_queue<_st, std::vector<_st>, COMP> AC;
std::priority_queue<_st, std::vector<_st>, NCOMP> realAC;   // 활성상태이지만 번식은 안함 
 
 
void debug()
{
    for (int i = 480; i < 520; i++) {
        for (int j = 480; j < 520; j++) {
            printf("%d", board[i][j]);
        }
        printf("\n");
    }
}
 
 
 
void input()
{
    // init
    memset(in, 0, sizeof(in));
    memset(board, 0, sizeof(board));
    nonAC = {};
    AC = {};
    realAC = {};
 
    // input
    scanf("%d %d %d", &N, &M, &K);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d", &in[i][j]);
            if (in[i][j] != 0) {
                nonAC.push({ 500 + i, 500 + j, in[i][j], 0 });
                board[500 + i][500 + j] = in[i][j];
            }
        }
    }
}
 
 
void activate(int time)
{
    while (!nonAC.empty()) {
        _st data = nonAC.top();
        if (data.t + data.X == time) {
            //printf("[activate]%d %d\n", data.r, data.c);
            nonAC.pop();
            AC.push({data.r, data.c, data.X, time});
            realAC.push({ data.r, data.c, data.X, time });
        }
        else if (data.t + data.X > time) return;
    }
}
 
 
void breed_cell(int time)
{
    // dir
    int dr[4] = { 0, 0, 1, -1 };
    int dc[4] = { 1, -1, 0, 0 };
 
 
    while (!AC.empty()) {
        _st data = AC.top();
        //printf("[breed]time : %d %d %d %d\n",time, data.r, data.c, data.t);
        if (data.t + 1 == time) {
            //printf("[breed]%d %d %d\n", data.r, data.c, data.t);
            AC.pop();
            for (int p = 0; p < 4; p++) {
                int nr = data.r + dr[p];
                int nc = data.c + dc[p];
 
                if (board[nr][nc] != 0) continue;
                nonAC.push({ nr, nc, data.X, time });
                board[nr][nc] = data.X;
            }
        }
        else if (data.t + 1 > time) return;
    }
}
 
 
void is_dead(int time)
{
    while (!realAC.empty()) {
        _st data = realAC.top();
        if (data.t + data.X == time) realAC.pop();
        else if (data.t + data.X > time) return;
    }
}
 
 
int simulation()
{
    for (int time = 1; time <= K; time++) {
        activate(time);
        breed_cell(time);
        is_dead(time);
    }
    return nonAC.size() + realAC.size();
}
 
 
 
int main()
{
    scanf("%d", &T);
    for (int t = 1; t <= T; t++) {
        input();
        int ans = simulation();
        printf("#%d %d\n",t, ans);
    }
    return 0;
}

1. 좌표공간이 무한히 확장가능하다고 했지만, 극단적인 경우를 생각해봐도 최대 600을 넘지 않는다. 

입력 좌표 (0, 0)에서 생명력 수치 X = 1인 세포가 300시간 동안 번식한다고 했을 때, 상 / 하 / 좌 / 우로 300개씩 번식할 수 있기 때문이다. 

괜히 적게 줘서 oob 나는 것 보다는 많이 주는게 낫다고 생각해서 (투머치 이긴 하지만) 1000 * 1000 맵으로 할당했다. 

 

2. 세포가 활성화되고, 번식되고, 죽는 과정은 activate -> breed cell -> is dead 함수를 거치면서 이루어진다. 

2-1. 세포는 생긴 시간(data.t) + 생명력 수치(data.X) 만큼의 시간이 지났을 때 활성화 된다. 

이때 번식가능한 세포 AC와 활성화된 세포 realAC를 따로 저장해주었다. 

2-2. 세포는 활성화 되고 단 한시간 동안만 번식이 가능하다. 

이때 생성된 세포는 nonAC에 담는다. 

2-3. 만약 현재 시간이 세포의 활성화된 시간(data.t) + 생명력 수치(data.X)와 같다면 죽는다. 이때 realAC에 있는 원소를 pop해준다.

 

3. 마지막으로 비활성 상태 + 활성 상태의 세포 수를 출력하라고 했으므로 nonAC와 realAC 각각의 사이즈를 출력한다. 

 

 

---

++ 좀더 똑똑하게 짠 과거의 나.. 

어떻게 생각한거냐 나자신.. ? 

하지만 논리적으로는 위의 코드가 맞다고 생각한다. 

#include <cstdio>
#include <queue>
#include <set>
using namespace std;

int T;
int N, M, K;

struct _st
{
	int x, y;   // 위치    
	int X;      // 생명력 수치
	int time;
};

struct COMP
{
	bool operator()(_st &a, _st &b) {
		return a.X < b.X;
	}
};

set<pair<int, int>> Point;

queue<_st> NC;    // 비활성 세포들
priority_queue<_st, vector<_st>, COMP> AC;  // 활성 세포들


void init()
{
	Point.clear();
	NC = {};
	AC = {};
}



void input()
{
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int X = 0;
			scanf("%d", &X);
			if (X != 0) {
				NC.push({ i, j, X, 1 });
				Point.insert({ i, j });
			}
		}
	}
}


void breed()
{
	static int dir_x[4] = { 0, 0 ,1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };

	queue<_st> Tmp_NC;
	priority_queue<_st, vector<_st>, COMP> Tmp_AC;

	//printf("[before NC]%d ", NC.size());
	//printf("[before AC]%d \n", AC.size());
	// 활성 세포들에 대하여 
	while (!AC.empty()) {
		_st data = AC.top();
		AC.pop();

		if (data.time == 1) {   // 번식한다. 
			for (int p = 0; p < 4; p++) {
				int nx = data.x + dir_x[p];
				int ny = data.y + dir_y[p];

				auto iter = Point.find({ nx, ny });
				if (iter != Point.end()) continue;      // 이미 존재하는 좌표면 스루
				else {
					Tmp_NC.push({ nx, ny, data.X, 1 });
					Point.insert({ nx, ny });
				}
			}
		}
		if (data.time == data.X) continue;  // 죽게된다. 
		Tmp_AC.push({ data.x, data.y, data.X, data.time + 1 }); // 활성상태 유지 
	}


	// 비활성 세포들에 대하여 
	while (!NC.empty()) {
		_st data = NC.front();
		NC.pop();

		if (data.time == data.X) Tmp_AC.push({ data.x, data.y, data.X, 1 });    // 활성상태 됨 
		else Tmp_NC.push({ data.x, data.y, data.X, data.time + 1 });
	}

	AC = Tmp_AC;
	NC = Tmp_NC;
	//printf("[after NC]%d ", NC.size());
	//printf("[after AC]%d \n", AC.size());
}


int simulation()
{
	for (int k = 1; k <= K; k++) {
		//printf("\n%d==============\n", k);
		breed();
	}
	return NC.size() + AC.size();
}


int main()
{
	scanf("%d", &T);
	for (int t = 0; t < T; t++) {
		init();
		input();
		int ans = simulation();
		printf("#%d %d\n", t + 1, ans);
	}
	return 0;
}

격자 공간이 무한히 늘어날 수 있다고 해서 set썼다. (어차피 좌표 중복체크만 하면 되므로..)

그리고 생명력 수치가 높은 것 부터 꺼내야 했기 때문에 priority queue썼다.