5648 원자 소멸 시뮬레이션

1. x, y 좌표를 각각 0~2000 으로 놓는다.

 

2. 한칸에 최대 4개의 원자가 모일 수 있으므로 여유공간 4개를 준다.

 

3. 0.5초 단위로 충돌하는 경우와 1초단위로 충돌하는 경우로 나누어 처리한다.

 

#include <stdio.h>
#define MAX_SZ 2002

struct Node {
	int x, y, dir, k;
	Node() {}
	Node(int x, int y, int d, int k) :x(x), y(y), dir(d), k(k) {}
};

int map[MAX_SZ][MAX_SZ][4];
int cnt[MAX_SZ][MAX_SZ];
int t, n;
Node node[1000];
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };
bool check[1000];

void init() {
	for (int i = 0; i < MAX_SZ; i++) {
		for (int j = 0; j < MAX_SZ; j++) {
			cnt[i][j] = 0;
		}
	}
}

int main() {
	scanf("%d", &t);

	for (int tc = 1; tc <= t; tc++) {
		scanf("%d", &n);

		init();

		for (int i = 0; i < n; i++) {
			check[i] = true;
			scanf("%d %d %d %d", &node[i].x, &node[i].y, &node[i].dir, &node[i].k);
			node[i].x += 1000;
			node[i].y += 1000;

			int x = node[i].x;
			int y = node[i].y;
			int idx = cnt[x][y];

			//맵에 기록해주기
			map[x][y][idx] = i;
			cnt[x][y]++;
		}

		int time = 2001;
		int res = 0;
		int end = n;

		while (time--) {
			if (end == 0) break;

			//0.5초단위 충돌에 대한 처리
			for (int i = 0; i < n; i++) {
				if (!check[i]) continue; //이미 터진 원자면 continue

				int x = node[i].x;
				int y = node[i].y;

				int ax = x + dx[node[i].dir];
				int ay = y + dy[node[i].dir];

				//맵 범위를 벗어나는 경우
				if (ax < 0 || ay < 0 || ax>2000 || ay>2000) {
					check[i] = false;
					cnt[x][y] = 0;
					continue;
				}

				if (cnt[ax][ay] != 0) {
					int next = map[ax][ay][0];
					if ((node[i].dir == 0 && node[next].dir == 1) ||
						(node[i].dir == 1 && node[next].dir == 0) ||
						(node[i].dir == 2 && node[next].dir == 3) ||
						(node[i].dir == 3 && node[next].dir == 2)) {

						cnt[x][y] = 0;
						cnt[ax][ay] = 0;
						check[i] = false;
						check[next] = false;
						end -= 2;

						res += node[i].k + node[next].k;
					}
				}
			}

			//원자 한칸씩 이동시키기.

			//맵에서 지우기
			for (int i = 0; i < n; i++) {
				if (!check[i]) continue;

				int x = node[i].x;
				int y = node[i].y;
				cnt[x][y] = 0;
			}

			//다음칸 맵에 기록하기
			for (int i = 0; i < n; i++) {
				if (!check[i]) continue;

				int x = node[i].x += dx[node[i].dir];
				int y = node[i].y += dy[node[i].dir];
				if (x < 0 || y < 0 || x>2000 || y>2000) {
					check[i] = false;
					continue;
				}

				map[x][y][cnt[x][y]] = i;
				cnt[x][y]++;
			}

			//충돌 처리하기
			for (int i = 0; i < n; i++) {
				if (!check[i]) continue;

				int x = node[i].x;
				int y = node[i].y;

				if (cnt[x][y] > 1) {
					end -= cnt[x][y];

					for (int j = 0; j < cnt[x][y]; j++) {
						int next = map[x][y][j];
						check[next] = false;
						res += node[next].k;
					}

					cnt[x][y] = 0;
				}
			}
		}

		printf("#%d %d\n", tc, res);

	}
}