[SWEA] 2382. 미생물 격리
문제 접근
줄기세포 배양 문제를 풀며 priority_queue 자료구조를 사용하는 문제를 풀어봐야겠다는 생각이 들어 예전에 푼 문제지만 다시 풀어보았다.
예전 코드를 다시 보니 굉장히 주먹구구라 다시 풀어보길 잘 했다는 생각이 들었음.
처음에는 prioirty_queue를 안 써서 구현했는데 문제 조건을 자세히 살펴보니 prioirty_queue 를 왜 써야하는지 알 수 있어서 의미 있었다.
순차적으로 구현하면 된다.
- 미생물 군집이 이동함
- 약품이 칠해진 셀에 도달한다면
이동방향을 반대로 설정하고, 군집 내 미생물 절반이 죽는다. (0이 될 경우 군집은 사라진다.) - 두 개 이상의 군집이 한 셀에 모일 경우, 군집은 합쳐진다.
미생물 수는 군집의 미생물들의 합이 되고, 이동방향은 군집들 중 미생물 수가 가장 많은 군집의 이동방향이 된다.
3번 조건이 생각할 거리가 많았다.
처음에는 단순하게 생각해서 map에 이미 미생물이 있으면 그 미생물과 현재 traverse하는 미생물의 크기를 비교했는데, 이 경우 3개 이상의 미생물이 같은 공간에 있을 경우를 고려하지 못 하는 오류가 생긴다!
그래서 priority_queue를 사용해서 군집의 크기대로 정렬하는 방법을 사용.
이렇게 구현할 경우, map에 이미 미생물이 있다는 것은 현재 traverse하는 미생물보다 더 큰 크기의 미생물이 이미 map에 있다는 것을 의미한다.
'map에 이미 미생물이 있을 경우, traverse하는 미생물이 사라짐.' 을 구현하기 위해 미생물을 나타내는 자료구조인 node에 idx변수를 두어 이를 통해 vector에 바로 접근할 수 있게 하였다.
map을 0으로 초기화하는 바람에 디버깅을 좀 했는데, vector의 idx는 0부터 시작하므로 map을 -1로 초기화를 해주어야 한다.
풀이
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
typedef struct node {
int idx;
int x;
int y;
long cnt;
int dir;
bool is_live;
};
struct cmp {
bool operator()(node a, node b) {
return a.cnt < b.cnt;
}
};
vector<node> nodes;
priority_queue<node, vector<node>, cmp> Move;
int T, N, M, K, rst;
int map[100][100];
int dx[] = { 0, -1, 1, 0, 0 };
int dy[] = { 0, 0, 0, -1, 1 };
void input() {
nodes.clear();
memset(map, 0, sizeof(map));
cin >> N >> M >> K;
for (int i = 0; i < K; i++) {
int r, c, cnt, dir;
cin >> r >> c >> cnt >> dir;
int idx = nodes.size();
nodes.push_back({ idx, r, c, cnt, dir, true });
}
}
int is_side(int x, int y) {
if (x == 0 || x == N - 1 || y == 0 || y == N - 1) return true;
return false;
}
int reverse(int dir) {
switch (dir) {
case 1: return 2;
case 2: return 1;
case 3: return 4;
case 4: return 3;
}
}
void move() {
memset(map, -1, sizeof(map));
for (int i = 0; i < nodes.size(); i++) {
if (nodes[i].is_live) Move.push(nodes[i]);
}
while (!Move.empty()) {
int x = Move.top().x;
int y = Move.top().y;
int dir = Move.top().dir;
int idx = Move.top().idx;
Move.pop();
int nx = x + dx[dir];
int ny = y + dy[dir];
if (is_side(nx, ny)) {
nodes[idx].dir = reverse(nodes[idx].dir);
nodes[idx].cnt = nodes[idx].cnt / 2;
if (nodes[idx].cnt == 0) nodes[idx].is_live = false;
}
if (map[nx][ny] == -1) { // 미생물이 없는 경우
map[nx][ny] = idx;
nodes[idx].x = nx; nodes[idx].y = ny;
}
else { // 미생물이 있는 경우 -> 기존의 미생물이 무조건 더 큰 군집이다.
nodes[map[nx][ny]].cnt += nodes[idx].cnt;
nodes[idx].is_live = false;
}
}
}
void solve() {
while (M-- > 0) {
move();
}
rst = 0;
for (int i = 0; i < nodes.size(); i++) {
if (nodes[i].is_live) rst += nodes[i].cnt;
}
}
int main() {
cin >> T;
for (int tc = 1; tc <= T; tc++) {
input();
solve();
cout << "#" << tc << " " << rst << endl;
}
}
Author And Source
이 문제에 관하여([SWEA] 2382. 미생물 격리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kyoung99u/SWEA-미생물-격리저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)