[SWEA] 5653번: 줄기세포배양

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

SW Expert Academy

 

문제 이해

일단 배양 접시의 크기를 주지 않았지만 최대 300번 시뮬을 돌릴 수 있고, 처음 주어지는 세포 범위의 크기가 50이라 했으며, 세포는 가장 생명력이 약한 친구(1)도 2번 동안은 살아있으므로 최대 150칸 뻗어나간다는 것을 알 수 있다.

그래서 넉넉하게 150 *2 + 50 + 여유분 --> 이 정도로 맵 사이즈를 지정하면 된다.

 

세포의 좌표, 생명력, 활성화 여부 등을 배열에 저장한다.

typedef struct st {
	int y, x, l, a; // life, alive
	int m; // 수명
}CELL;
CELL c[(MAXXY + 100 + MAXXY) * (MAXXY + 100 + MAXXY) + 10];

배열에 있는 세포들은 다 활성화 상태인 배열이다.

이 배열은 매 단계마다 살아있는 애들만 다시 채워줄 것이다.

 

입력을 받을 때 세포이면 다 이 세포 배열에 넣어준다.

 

그리고 이제 시간의 흐름에 따라 시뮬레이션을 돌린다. 

이때 세포의 생명력에 따라서 세포가 활성화되는 시간과 죽는 시간이 달라지기에 주의해야 한다.

 

Simulation()

나는 l에 남은 생명력을 담고, m에 세포의 원래 수명을 적고, a는 활성화 여부를 담았다.

 

세포는 활성화 되지 않은 상태일 때 (a==0)

• l(생명력) 이 줄어들고, 
• l == -1 이면 번식하고 소멸을 위한 단계에 돌입한다.
• 이때 다시 생명력을 l로 채워준다. 왜냐하면 세포는 번식 후에도 본인 생명력-1의 시간만큼 살아있기 때문이다. 

 

다음으로는 활성화된 세포인지 확인한다.

• 생명력(l) 을 줄여준다.
• 만약 생명력이 0이하가 되면 죽는다.
• 윗 단계에서 갓 활성화된 애도 l-- 해준다. 어차피 세포는 번식 후 생명력-1 의 시간이 지나면 죽는다
• 죽었으면 다시 세포 배열에 넣지 않는다

void Simulation(int k) {
	memset(tmpc, 0, sizeof(tmpc));
	tmpccnt = 0;

	// 모든 세포에 대해서
	for (int i = 0; i < ccnt; i++) {
		if (map[c[i].y][c[i].x] != c[i].m) continue;
		if(c[i].a == 0){ // 활성화 전
			c[i].l--;
			if (c[i].l == -1) { // 번식할 것
				Spread(c[i].y, c[i].x, c[i].m, k);
				c[i].l = map[c[i].y][c[i].x];
				c[i].a = 1;
			}
		} // 활성화 됨
		if(c[i].a == 1){
			c[i].l--;
			if (c[i].l <= 0) {
				map[c[i].y][c[i].x] = -1; // 죽음
				continue;
			}
		}
		tmpc[tmpccnt++] = c[i];
	}
	memcpy(c, tmpc, sizeof(c));
	ccnt = tmpccnt;
}

이 부분이 어렵지 나머지는 어렵지 않다.

 

세포가 번식하는 과정을 살펴보면

Spread()

4방을 탐색하면서

• 빈칸이면 배양한다
• 죽은 세포이면 못배양한다
• 만약 배양이 된 칸인데, 나보다 먼저 단계에 만들어졌으면 못배양한다
• 만약 나랑 같은 단계에 만들어졌는데, 나보다 생명력이 크면 못배양한다

이 조건들을 다 통과했다면 배양한다.

void Spread(int y, int x, int m, int k) {
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (map[ny][nx] == -1) continue; // 죽은 세포가 존재
		if (tmap[ny][nx] != 0 && tmap[ny][nx] < k) continue; // 나보다 전에 생성된 친구
		if(tmap[ny][nx] == k){ // 같은 시간에 만들어졌는데 나보다 생명력 세다
			if (map[ny][nx] >= m) continue;
		}
		map[ny][nx] = m;
		tmap[ny][nx] = k;
		tmpc[tmpccnt].y = ny, tmpc[tmpccnt].x = nx;
		tmpc[tmpccnt].l = m, tmpc[tmpccnt].a = 0;
		tmpc[tmpccnt++].m = m;
	}
}

 

 

getCnt()

최종 답을 구하는 함수.

처음에는 그냥 세포 배열의 크기를 답으로 줬다.

그랬더니 45번째 테케에서 틀렸다.

 

생각해보니 내 세포 배열에는 위에 하이라이트를 친 저 부분이 중복되어 있다.

즉, 생명력 2인 친구가 어느 칸에 배양되었는데, 같은 단계에서 세포 3이 배양하려고 한다.

map에 있는 값이 3보다 작으니까 무시하고 map에 3으로 덮어씌운다.

이때 이미 생명력2인 친구가 배양한 세포가 세포 배열에 들어가있다. 하지만 얘는 유효한 세포가 아니다.

그래서 무시되어야 한다.

 

이걸 시뮬 돌릴 때는 거를 수 있도록

		if (map[c[i].y][c[i].x] != c[i].m) continue;

조건을 줬었는데, 생각해보니 답 구할 때도 이 경우를 걸러줘야 하더라!

 

그래서 별도 함수를 만들어서 cnt를 다시 세준 것이다.

int getCnt(void) {
	int cnt = 0;
	for (int i = 0; i < ccnt; i++) {
		if (map[c[i].y][c[i].x] != c[i].m) continue;
		cnt++;
	}
	return cnt;
}

 

전체 코드

#include <stdio.h>
#include <string.h>
#define MAXXY 151

int T, K, N, M;
int map[MAXXY+100+ MAXXY][MAXXY + 100 + MAXXY];
int tmap[MAXXY + 100 + MAXXY][MAXXY + 100 + MAXXY];

typedef struct st {
	int y, x, l, a; // life, alive
	int m; // 수명
}CELL;
CELL c[(MAXXY + 100 + MAXXY) * (MAXXY + 100 + MAXXY) + 10];
CELL tmpc[(MAXXY + 100 + MAXXY) * (MAXXY + 100 + MAXXY) + 10];
int ccnt;
int tmpccnt;

void Get_Input(void) {
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &map[MAXXY + i + 5][MAXXY + j + 5]);
			if (map[MAXXY + i + 5][MAXXY + j + 5] != 0) {
				c[ccnt].y = MAXXY +i+5, c[ccnt].x = MAXXY +j+5;
				c[ccnt].l = map[MAXXY + i + 5][MAXXY + j + 5];
				c[ccnt].a = 0;
				c[ccnt++].m = map[MAXXY + i + 5][MAXXY + j + 5];
				tmap[MAXXY + i + 5][MAXXY + j + 5] = -1;
			}
		}
	}
}

int dy[] = { 0, 0, 1, -1 };
int dx[] = { 1, -1, 0, 0 };

void Spread(int y, int x, int m, int k) {
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (map[ny][nx] == -1) continue; // 죽은 세포가 존재
		if (tmap[ny][nx] != 0 && tmap[ny][nx] < k) continue; // 나보다 전에 생성된 친구
		if(tmap[ny][nx] == k){ // 같은 시간에 만들어졌는데 나보다 생명력 세다
			if (map[ny][nx] >= m) continue;
		}
		map[ny][nx] = m;
		tmap[ny][nx] = k;
		tmpc[tmpccnt].y = ny, tmpc[tmpccnt].x = nx;
		tmpc[tmpccnt].l = m, tmpc[tmpccnt].a = 0;
		tmpc[tmpccnt++].m = m;
	}
}

void Simulation(int k) {
	memset(tmpc, 0, sizeof(tmpc));
	tmpccnt = 0;

	// 모든 세포에 대해서
	for (int i = 0; i < ccnt; i++) {
		if (map[c[i].y][c[i].x] != c[i].m) continue;
		if(c[i].a == 0){ // 활성화 전
			c[i].l--;
			if (c[i].l == -1) { // 번식할 것
				Spread(c[i].y, c[i].x, c[i].m, k);
				c[i].l = map[c[i].y][c[i].x];
				c[i].a = 1;
			}
		} // 활성화 됨
		if(c[i].a == 1){
			c[i].l--;
			if (c[i].l <= 0) {
				map[c[i].y][c[i].x] = -1; // 죽음
				continue;
			}
		}
		tmpc[tmpccnt++] = c[i];
	}
	memcpy(c, tmpc, sizeof(c));
	ccnt = tmpccnt;
}

void Init(void) {
	memset(map, 0, sizeof(map));
	memset(c, 0, sizeof(c));
	memset(tmap, 0, sizeof(tmap));
	ccnt = 0;
}

int getCnt(void) {
	int cnt = 0;
	for (int i = 0; i < ccnt; i++) {
		if (map[c[i].y][c[i].x] != c[i].m) continue;
		cnt++;
	}
	return cnt;
}

int main(void) {
	scanf("%d", &T);
	for (int t = 1; t <= T; t++){
		Init();
		Get_Input();
		for (int k = 1; k <= K; k++) {
			// 시뮬레이션
			Simulation(k);
		}
		int res = getCnt();
		printf("#%d %d\n", t, res);
	}
	return 0;
}