[SWEA] 2382. 미생물 격리

문제 접근

줄기세포 배양 문제를 풀며 priority_queue 자료구조를 사용하는 문제를 풀어봐야겠다는 생각이 들어 예전에 푼 문제지만 다시 풀어보았다.
예전 코드를 다시 보니 굉장히 주먹구구라 다시 풀어보길 잘 했다는 생각이 들었음.
처음에는 prioirty_queue를 안 써서 구현했는데 문제 조건을 자세히 살펴보니 prioirty_queue 를 왜 써야하는지 알 수 있어서 의미 있었다.

순차적으로 구현하면 된다.

1. 미생물 군집이 이동함
2. 약품이 칠해진 셀에 도달한다면
   이동방향을 반대로 설정하고, 군집 내 미생물 절반이 죽는다. (0이 될 경우 군집은 사라진다.)
3. 두 개 이상의 군집이 한 셀에 모일 경우, 군집은 합쳐진다.
   미생물 수는 군집의 미생물들의 합이 되고, 이동방향은 군집들 중 미생물 수가 가장 많은 군집의 이동방향이 된다.

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;
	}
}