SWEA 5648 원자 소멸 시뮬레이션

1. 다른 문제와 달리 좌표평면 상의 좌표가 주어진다.

좌표가 가로위치 -> 세로위치 순으로 주어지며,

오른쪽 아래 방향이 가로위치와 세로위치가 증가하는 방향이다.

 

2. while(1)의 탈출조건인 ctr <= 1를 잘못 배치했다.

ctr <= 1을 '이동, 소멸 대상 판별'(e.i. for(a))와 '소멸, 초기화'(e.i. for(ci)) 사이에 배치하여,

마지막으로 남은 원자에 대해서는 초기화가 진행되지 않았고,

다음 테스트케이스부터 초기화가 되지 않은 자료구조 시작하여 런타임 에러가 발생했다.

탈출은 후처리가 완료된 다음, 초기화 누락이 런타임 에러 야기 가능

 

3. 인덱스를 0으로 만들어 초기화

매번 충돌 후 cld의 크기인 cldn이 0으로 초기화되어

차회에 cld가 0부터 채워지기 때문에 개별 원소에 대한 초기화 overhead를 덜 수 있다.

 

코드:

#include <iostream>
using namespace std;

int T, N;
int vst[4001][4001];
int cld[1001][4], cldn[1001], c;
int ctr;

struct info {
	int x, y, d, k;
};
info atoms[1000];

const int dx[] = { 0, 0, -1, 1 };
const int dy[] = { 1, -1, 0, 0 };
int main() {
	cin >> T;
	for (int tc = 1; tc <= T; ++tc) {
		cin >> N;
		for(int a = 0; a < N; ++a) {
			int x, y, d, k; cin >> x >> y >> d >> k;
			atoms[a] = { 2 * (x + 1000), 2 * (y + 1000), d, k };
		}
		int ans = 0;
		while (1) {
			c = 1;
			ctr = 0;
			for (int a = 0; a < N; ++a) {
				if (atoms[a].x == -1) continue;

				atoms[a].x += dx[atoms[a].d];
				atoms[a].y += dy[atoms[a].d];
				if (atoms[a].x < 0 || 4000 < atoms[a].x || atoms[a].y < 0 || 4000 < atoms[a].y) {
					atoms[a].x = -1; continue;
				}
				++ctr;

				if (vst[atoms[a].x][atoms[a].y])
					cld[vst[atoms[a].x][atoms[a].y]][cldn[vst[atoms[a].x][atoms[a].y]]++] = a;
				else {
					vst[atoms[a].x][atoms[a].y] = c;
					cld[c][cldn[c]++] = a;
					++c;
				}
			}
			for (int ci = 1; ci < c; ++ci) {
				for (int cldi = 0; cldi < cldn[ci]; ++cldi) {
					vst[atoms[cld[ci][cldi]].x][atoms[cld[ci][cldi]].y] = 0;
					if (cldn[ci] > 1) {
						ans += atoms[cld[ci][cldi]].k;
						atoms[cld[ci][cldi]].x = -1;
					}
				}
				cldn[ci] = 0;
			}
			if (ctr <= 1) break;
		}
		cout << '#' << tc << ' ' << ans << '\n';
	}
	return 0;
}