요약
우선순위 큐 -> 큐 -> 우선순위 큐(used가 있으면 더해줬다.)
두 군집이 같은 곳에서 만난 경우,cnt는 합쳐지고 d는 cnt가 더 큰 곳의 것을 따르게 되어야함. used에 q에 있는 것을 전부 옮겼음.
문제
① 최초 각 미생물 군집의 위치와 군집 내 미생물의 수,이동 방향이 주어진다.
약품이 칠해진 부분에는 미생물이 배치되어 있지 않다.
이동방향은 상, 하, 좌, 우 네 방향 중 하나이다.
② 각 군집들은 1시간마다 이동방향에 있는 다음 셀로 이동한다.
③ 미생물 군집이 이동 후 약품이 칠해진 셀에 도착하면
군집 내 미생물의 절반이 죽고, 이동방향이 반대로 바뀐다.
살아남은 미생물 수 = 원래 미생물 수를 2로 나눈 후 소수점 이하를 버림 한 값
따라서 군집에 미생물이 한 마리 있는 경우 살아남은 미생물 수가 0이 되기 때문에,
군집이 사라지게 된다.
④ 이동 후 두 개 이상의 군집이 한 셀에 모이는 경우 군집들이 합쳐지게 된다.
합쳐 진 군집의 미생물 수는 군집들의 미생물 수의 합이며,
이동 방향은 군집들 중 미생물 수가 가장 많은 군집의 이동방향이 된다.
합쳐지는 군집의 미생물 수가 같은 경우는 주어지지 않으므로 고려하지 않아도 된다.
[제약사항]
1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 5초
2. 구역의 모양은 정사각형으로 주어지며, 한 변의 셀의 개수 N은 5이상 100이하의 정수이다. (5 ≤ N ≤ 100)
3. 최초 배치되어 있는 미생물 군집의 개수 K는 5이상 1,000이하의 정수이다. (5 ≤ K ≤ 1,000)
4. 격리 시간 M은 1이상 1,000이하의 정수이다. (1 ≤ M ≤ 1,000)
5. 최초 약품이 칠해진 가장자리 부분 셀에는 미생물 군집이 배치되어 있지 않다.
6. 최초에 둘 이상의 군집이 동일한 셀에 배치되는 경우는 없다.
7. 각 군집 내 미생물 수는 1 이상 10,000 이하의 정수이다.
8. 군집의 이동방향은 상하좌우 4방향 중 한 방향을 가진다. (상: 1, 하: 2, 좌: 3, 우: 4)
9. 주어진 입력으로 진행하였을 때, 동일한 셀에 같은 미생물 수를 갖는 두 군집이 모이는 경우는 발생하지 않는다.
10. 각 군집의 정보는 세로 위치, 가로 위치, 미생물 수, 이동 방향 순으로 주어진다. 각 위치는 0번부터 시작한다.
[입력]
각 테스트 케이스의 첫째 줄에는 구역의 한 변에 있는
셀의 개수 N, 격리 시간 M, 미생물 군집의 개수 K가 순서대로 주어지며,
다음 K줄에 걸쳐서 미생물 군집 K개의 정보가 주어진다.
미생물 군집의 정보는 세로 위치, 가로 위치, 미생물 수, 이동 방향 순으로 4개의 정수가 주어진다.
[출력]
M 시간 동안 이 미생물 군집들을 격리하였다.
M시간 후 남아 있는 미생물 수의 총합을 구하여라.풀이
#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
using namespace std;
struct Node {
int cnt, d;
};
int N, M, K;
int ans;
int map[100][100];
Node used[100][100];
// 미생물의 개수가 큰 순서대로 정렬
struct slime {
int row, col, cnt, d;
};
struct cmp {
bool operator()(slime a, slime b) {
if (a.cnt < b.cnt) return true;
return false;
}
};
vector<slime>v;
queue<slime>pq;
priority_queue<slime, vector<slime>, cmp>q;
// 인덱스로 이동방향을 설정 : - 상 하 좌 우
int dr[5] = { 0,-1,1,0,0 };
int dc[5] = { 0,0,0,-1,1 };
int BFS(int M) {
while (M > 0) {
while (!pq.empty()) {
slime Now = pq.front();
pq.pop();
int pr = Now.row;
int pc = Now.col;
int cntNow = Now.cnt;
int dNow = Now.d;
int nr = Now.row + dr[Now.d];
int nc = Now.col + dc[Now.d];
if (nr == 0 || nr == N - 1 || nc == 0 || nc == N - 1) {
if (dNow == 1 || dNow == 3) dNow++;
else dNow--;
cntNow = cntNow / 2;
}
q.push({ nr,nc,cntNow,dNow });
}
memset(used, 0, sizeof(used));
while (!q.empty()) {
slime Now = q.top();
q.pop();
if (used[Now.row][Now.col].d) {
used[Now.row][Now.col].cnt += Now.cnt;
}
else used[Now.row][Now.col] = { Now.cnt, Now.d };
}
ans = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (used[i][j].d) {
pq.push({ i,j,used[i][j].cnt,used[i][j].d });
ans += used[i][j].cnt;
}
}
}
M--;
}
while (!pq.empty()) {
pq.pop();
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie();
cout.tie();
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cin >> N >> M >> K;
for (int i = 0; i < K; i++) {
int row, col, cnt, d;
cin >> row >> col >> cnt >> d;
pq.push({ row,col,cnt,d });
map[row][col] = cnt;
}
ans = BFS(M);
cout << "#" << tc << " " << ans << "\n";
}
return 0;
}