SWEA 5653번: [모의 SW 역량테스트] 줄기세포 배양하기

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

SW Expert Academy

모의 역량테스트 중 하나인 줄기세포 배양하기 문제!!

요즘 출제되는 전형적인 시뮬레이션 문제이당(이동, 번식, 등등 시간 경과 후 결과)

 

세포 번식

생명력 X를 가진 비활성 세포는 X시간 후 활성 세포가 되고

활성 세포는 첫 1시간에 상하좌우로 번식(한 칸에 여러 세포가 시도할 경우 가장 큰 생명력을 선택),

X시간 후에는 죽은 세포가 된다

 

풀이 노트

이 문제 또한 각각의 자료를 저장 및 연산할 자료구조를 잘 선택해야 한다

나는 위의 노트처럼 문제를 보자마자 바로 #include부터 쓰면서 코딩하는 것이 아닌,

문제를 내가 알아볼 수 있게 정리하고 내가 생각하는 알고리즘을 대략적으로 구상했다.

이렇게 하면, 체계적으로 코딩을 할 수 있고

어느 부분에서 막혔다면 어느 부분의 알고리즘을 구체화 해야할 지 알 수 있다.

 

나는 노트에 정리한 내용을 바탕으로 {상태, 생명력, 시간}의 구조체 배열을 생성하고,

활성/비활성 세포들은 좌표 구조체 형태의 큐에 저장했다

그리고 활성상태에서 번식할 추가 세포들은 대기 큐에 미리 넣어준 다음,

좌표가 겹치지 않게 한 세포만 비활성 세포 큐에 넣어주었다

비활성 상태 세포들은 각각 count를 감소시켜주고 0인 세포는 활성세포 큐에 push

 

그리고 K시간이 지난 후 활성세포 큐와 비활성세포 큐의 사이즈를 더해주면 끝!

#include <cstdio>
#include <queue>
#define loc 400
using namespace std;
int tc, ans, n, m, k, dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
typedef struct {
	int r, c;
}point;
typedef struct {
	int state, X, cnt;
}cell;
cell map[1001][1001];
bool visit[1001][1001];
queue<point> A, N,W;
int main() {
	scanf("%d", &tc);
	for (int T = 1; T <= tc; T++) {
		scanf("%d%d%d", &n, &m, &k);
		for (int i = loc; i < loc + n; i++)
			for (int j = loc, d; j < loc + m; j++) {
				scanf("%d", &d);
				if (d) {
					map[i][j] = {3,d,d};
					N.push({ i,j });
				}
			}

		while (k--) {	//K초동안
			//활성세포 처리
			int nonActsize = N.size();
			for (int i = (int)A.size(); i >0 ; i--) {
				point cp = A.front(); A.pop();
				cell& cur = map[cp.r][cp.c];
				if (cur.cnt == cur.X)
					for (int d = 0, nx, ny; d < 4; d++) {
						ny = cp.r + dy[d], nx = cp.c + dx[d];
						if (!map[ny][nx].state
							|| (map[ny][nx].state == 4
								&& map[ny][nx].X < cur.X)) {
							map[ny][nx] = {4,cur.X,cur.X};
							if (!visit[ny][nx]) {
								W.push({ ny,nx });
								visit[ny][nx] = 1;
							}
						}
					}//4방향 번식
				cur.cnt--;	//생명력 감소
				if (!cur.cnt)	//사망
					cur.state = 1;
				else A.push(cp);
			}
			while (!W.empty()) {
				point cp = W.front(); W.pop();
				cell& cur = map[cp.r][cp.c];
				visit[cp.r][cp.c] = 0;
				cur.state = 3;
				N.push(cp);
			}

			for (int i = nonActsize; i >0 ; i--) {
				point cp = N.front(); N.pop();
				cell& cur = map[cp.r][cp.c];;
				if (!(--cur.cnt)) {
					cur.state = 2;
					cur.cnt = cur.X;
					A.push(cp);
				}
				else
					N.push(cp);
			}
		}
		ans = A.size() + N.size();

		printf("#%d %d\n", T, ans); ans = 0;
		while (!A.empty())A.pop();
		while (!N.empty())N.pop();
		for(int i=0;i<1000;i++)
			for(int j=0;j<1000;j++)
				if (map[i][j].state) {
					map[i][j] = { 0,0,0 };
				}

	}
	return 0;
}

모든 TC에서의 초기화에서 시간을 많이 잡아먹은 코드 😢

큐의 연산을 할 때는 계속 변하는 size에 유의해주도록 하자