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

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

SW Expert Academy

 

[풀이과정]

 

1. 세포의 번식은 무한하다. 따라서 최대 값의 배열 크기를 잡았다.

 * 1 <= N, M <= 50,    1 <= K <= 300 이다. 하지만 세포의 생명력이 1이여도 최소 2만큼이 소비된다.

 * 활성화되기까지 1이 걸리고 다음에 번식을 하기 때문에 최대 배열크기는 50 + (150 * 2)로 350을 구했다.

 

2. 이제 시간마다 세포가 살아있는 시간을 줄여주고 그에 맞게 활성화 상태, 죽은 세포로 구분을 해준다.

활성화 된 세포는 번식을 진행하면 된다. 번식 중 같은 곳을 향할 경우 더 생명력이 큰 세포로 채워준다.

 

소스코드

#include<stdio.h>
#include<vector>
#define MAX_NODE 350
using namespace std;
enum STATUS{
	NOT_USE,
	DIE,
};
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0 , 0, -1, 1};
struct cell {
	int status;
	int time;
	int val;
}typedef cell;
cell map[350][350];

int N, M, T, K, answer;
void bfs(pair<int, int> p)
{
	cell cur = map[p.second][p.first];
	for (int i = 0; i < 4; i++) {
		int nx = p.first + dx[i];
		int ny = p.second + dy[i];
		cell newCell = { STATUS::NOT_USE , cur.val * 2, cur.val };
		if (map[ny][nx].val == 0) {
			map[ny][nx] = newCell;
		}
		else {
			if (map[ny][nx].val * 2 != map[ny][nx].time) continue; //현재 넣은게 아니면!
			if (map[ny][nx].val < newCell.val) {
				map[ny][nx] = newCell;
			}
		}
	}
}
void solution()
{
	for (int i = 1; i <= K; i++) {
		vector<pair<int, int>> v;
		for (int y = 0; y < 350; y++) {
			for (int x = 0; x < 350; x++) {
				if (map[y][x].status == STATUS::DIE) continue;
				
				if (map[y][x].time == map[y][x].val) {
					v.push_back(make_pair(x, y));
				}
				map[y][x].time--;
				if (map[y][x].time == 0) {
					map[y][x].status = STATUS::DIE;
				}

			}
		}

		for (int j = 0; j < v.size(); j++) {
			bfs(v[j]);
		}
	}
	answer = 0;
	for (int y = 0; y < 350; y++) {
		for (int x = 0; x < 350; x++) {
			if (map[y][x].status == STATUS::DIE) continue;
			answer++;
		}
	}
}
void initMap()
{
	cell c = { STATUS::DIE,0,0 };
	for (int i = 0; i < MAX_NODE; i++) {
		for (int j = 0; j < MAX_NODE; j++) {
			map[i][j] = c;
		}
	}
}
int main()
{
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++) {
		scanf("%d %d %d", &N, &M, &K);
		initMap();
		for (int i = 150; i < 150 + N; i++) {
			for (int j = 150; j < 150 + M; j++) {
				int n;
				scanf("%d", &n);
				cell c = { n > 0 ? STATUS::NOT_USE : STATUS::DIE, n * 2, n };
				map[i][j] = c;
			}
		}
		solution();
		printf("#%d %d\n", tc, answer);
	}
}

 

 

[결과]

 

매 시간 마다 모든 맵을 계속 뒤지는 방식을 사용해서 시간초과가 날 수도 있을거라 생각했으나 통과되었다.

vector를 하나 추가해 살아 있는 세포 값만 넣어줘도 시간이 많이 줄 것 같다.