문제 URL: swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
문제 접근법 : 시뮬레이션 문제니까 나와있는 조건을 그대로 합니다.
접근 1: 세포라는 구조체를 만들고 상태와 좌표, 라이프주기와 원래 가지고있던 고유의 라이프를 만듭니다.
접근 2: 원래 라이프 시간동안 살아있을수 있으니 매시간마다 1씩 줄여주고 0이되면 활성상태를 바꾸고 원래 고유의 라이프에 다시 라이프주기에다가 넣어줍니다.
접근 3: 첫 1시간 동안 상, 하, 좌, 우 네 방향으로 동시에 번식 & 셀에 동시 번식하려고 하는 경우 생명력 수치가 높은 줄기 세포가 해당 그리드 셀을 혼자서 차지하게 된다-> 생명력 수치가 높은것을 번식 즉 고유라이프가 큰것을 저장해주면됩니다.
접근 4: K시간 후 살아있는 줄기 세포(비활성 상태 + 활성 상태)의 총 개수를 구하는 프로그램 -> 큐에 항상 비활성 상태와 활성상태만 저장하기때문에 K시간후 남아있는 큐사이즈만 리턴하면 살아있는 세포들의 개수를구할수있습니다.
접근 5: 줄기 세포의 크기에 비해 배양 용기의 크기가 매우 크기 때문에 시뮬레이션에서 배양 용기의 크기는 무한하다고 가정한다. -> 이것을 할려면 재생할때 Y,X의좌표가 음수가나오는 경우가 많아 MAP의 사이즈를 크게 잡고 Y,X의좌표의 기준점을 적당히 큰곳에 잡아야하는데 귀찮아서 map의 자료구조를 사용해서 키값을 pair 구조로 사용하면 음수처리에 대한 고민을 할필요가 없습니다. 다만 탐색속도는 조금 느리지만 문제를 해결하는데 괜찮습니다.
소스코드:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <queue>
using namespace std;
int n, m, k;
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 };
struct cell{
int state, life, templife, y, x;
cell(int y, int x, int state, int life, int templife) :y(y), x(x), state(state), life(life), templife(templife){}
cell(){}
};
map<pair<int, int>, int> visit;
int bfs(){
queue<cell> q;
for (auto it : visit)//처음 입력받은것을 큐에넣어줌
q.push({ it.first.first, it.first.second, 0, it.second, it.second });//y,x좌표와 상태, 라이프넣어줌
int time = 0;
while (!q.empty()){
int qsize = q.size();//매초마다 해당 세포들 변화하는것만 상태변화하기위해
map<pair<int, int>, int> exp;
if (time >= k)//time==k까지만 탐색
break;
while (qsize--){
int y = q.front().y;
int x = q.front().x;
int state = q.front().state;
int life = q.front().life;
int templife = q.front().templife;
q.pop();
if (state == 0){//비활성상태
if (life - 1 == 0)
q.push({ y, x, state + 1, templife, templife });//활성상태로 변화시켜야함
else
q.push({ y, x, state, life - 1, templife });//라이프만 깎으면됨
}
else if (state == 1){//활성상태
if (life == templife){//활성상태일때 첫1시간만 네방향으로 동시에 번식한다
for (int i = 0; i < 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if (visit.count({ ny, nx }) == 0)
exp[{ny, nx}] = max(exp[{ny, nx}], templife);//두개이상의 줄기세포가 하나의 그리드 셀에 동시 번식하는경우
}
}
if (life - 1>0)//life만 줄여줌 굳이 state값 2인것은 필요없음
q.push({ y, x, state, life - 1, templife });
}
}
for (auto it : exp){//두개이상의 줄기세포중 가장큰것을 q에넣고 visit처리까지 다해줘야함
visit[{it.first.first, it.first.second}] = 1;
q.push({ it.first.first, it.first.second, 0, it.second, it.second });
}
time++;
}
return q.size();//큐안에있는게 활성상태와 비활성상태니 그개수들이 전부 큐에 저장되어있어 큐사이즈만 반환하면됨
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int te;
cin >> te;
for (int test = 1; test <= te; test++)
{
visit.clear();
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
int t;
cin >> t;
if (t>0)//여기 입력받은 visit은 라이프 주기를 저장해야함
visit[{i, j}] = t;
}
}
cout << "#" << test << " " << bfs() << "\n";
}
}
|
cs |
모르는점 혹은 궁금한점 혹은 논리적으로 잘못된점이 있다면 언제든지 댓글을 이용해주시길 바랍니다.
'SWEA' 카테고리의 다른 글
| [SWEA] 5650 핀볼 게임(모의 SW 역량테스트) (0) | 2020.09.30 |
|---|---|
| [SWEA] 1941 등산로 조성(모의 SW 역량테스트) (0) | 2020.09.30 |
| [SWEA] 4013 특이한 자석 (모의 SW 역량테스트) (0) | 2020.09.27 |
| [SWEA] 9940 순열1 (0) | 2020.09.15 |
| [SWEA] 7792 반장 선출 (0) | 2020.09.15 |
