https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo
영역의 범위가 주어지지 않지만, 안전한 영역으로 잡아줄 수 있다. k의 상한선이 주어지기 때문에.
그에 맞춰서 map을 잡아주고, 불필요한 탐색을 피하기 위해서 좌표 정보를 벡터에 저장해두고, 그 벡터를 이용해서 필요한 곳만 탐색한다.
구조체에는 활성이 지속되는 시간, 활성 시작 시간, 죽는 시간, 상태를 저장한다.
이 정보를 이용해서 다음과 같은 알고리즘을 구현한다.
1. 활성 상태에 있는 세포를 BFS해준다. 한 칸씩만 움직이기 때문에 새로 큐에 삽입하거나 할 필요가 없다. 사전에 필요한만큼 미리 큐에 넣어두고 돌리면 된다.
2. 활성 시간, 비활성 시간이 된 것들의 상태를 변경해준다.
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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 | #include<iostream> #include<queue> #include<vector> using namespace std; typedef pair<int, int> pii; struct Info { int actTime, deathTime, duration = -1, state = -3; //0 1 -1, -2 비활 활 죽음 방금생김 };// 활성화시작시간, 비활시간, 유지기간, 상태 const int dr[4] = { 0,0,1,-1 }; const int dc[4] = { 1,-1,0,0 }; typedef pair<int, int> pii; int row, col, k; Info map[701][701]; queue<pii> q; vector<pii> v; vector<pii> pos; //위치정보 void bfs(int Time) { int qs = q.size(); while (qs--) { pii cur = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int nr = cur.first + dr[i]; int nc = cur.second + dc[i]; //나가는 경우 없음 //if (vis[nr][nc]) continue; if (map[nr][nc].state == 0 || map[nr][nc].state == -1 || map[nr][nc].state == 1) continue; if (map[nr][nc].duration == -1 || (map[nr][nc].state == -2 && map[cur.first][cur.second].duration >map[nr][nc].duration)) { Info tmp; tmp.duration = map[cur.first][cur.second].duration; tmp.actTime = Time + map[cur.first][cur.second].duration; tmp.deathTime = tmp.actTime + tmp.duration; tmp.state = -2; //방금생김 map[nr][nc] = tmp; v.push_back({ nr, nc }); // 나중에 state 바꾸기 위함 pos.push_back({ nr, nc }); //위치 정보에 추가 } } } for (int i = 0; i < v.size(); i++) { //state 바꾸고 bfs 종료 map[v[i].first][v[i].second].state = 0; } v.clear(); } void process() { for (int tm = 1 ; tm <= k; tm++) { //i = 시간 for (int i = 0; i < pos.size(); i++) { int r = pos[i].first; int c = pos[i].second; if (map[r][c].state == 1) q.push({ r, c }); } bfs(tm); //활성된애들 bfs //활성시간, 비활성시간 체크해서 업데이트 for (int i = 0; i < pos.size(); i++) { int r = pos[i].first; int c = pos[i].second; if (map[r][c].actTime == tm) map[r][c].state = 1; if (map[r][c].deathTime == tm) map[r][c].state = -1; } } } int main(void) { //setbuf(stdout, NULL); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; cin >> T; for (int t = 1; t <= T; t++) { cin >> row >> col >> k; for (int i = 0; i < row; i++) for (int j = 0; j < col; j++) { Info tmp; cin >> tmp.duration; if (tmp.duration == 0) continue; tmp.actTime = tmp.duration; tmp.deathTime = tmp.actTime + tmp.duration; pos.push_back({ 350 + i, 350 + j }); //위치 저장 map[i + 350][j + 350] = tmp; } process(); int ans = 0; for (int i = 0; i < pos.size(); i++) { int r = pos[i].first; int c = pos[i].second; if (map[r][c].state == 0 || map[r][c].state == 1) ans++; //죽지 않은 것들 } cout << "#" << t << ' ' << ans << '\n'; //map 초기화 for (int i = 0; i < pos.size(); i++) { int r = pos[i].first; int c = pos[i].second; Info tmp; map[r][c] = tmp; } pos.clear(); } return 0; } | cs |
'알고리즘 문제 풀이 > 삼성 SW Expert Academy' 카테고리의 다른 글
SWEA 5650: 핀볼 게임 (C++) (0) | 2019.10.17 |
---|---|
SWEA 1767: 프로세서 연결하기 (C++) (0) | 2019.10.17 |
SWEA 2117: 홈 방범 서비스 (C++) (0) | 2019.10.16 |
SWEA 2382: 미생물 격리 (C++) (0) | 2019.10.16 |
SWEA 2383: 점심 식사시간 (C++) (0) | 2019.10.15 |