SWEA 5648번: [모의 SW 역량테스트] 원자 소멸 시뮬레이션

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRFInKex8DFAUo

SW Expert Academy

 

원자 소멸 시뮬레이션은

2차원 좌표에 있는 원자들이 고유한 방향과 에너지를 가지고 있을 때,

충돌을 통해 소멸하는 원자들의 에너지의 총 합을 구하는 문제이다

(1,0)과 (4,0)은 (2.5,0)에서 만나기 때문에, 위치 좌표가 정수 범위를 벗어난다(처음에 이 고민에서 막혔다)

그렇기 때문에 좌표계를 * 2 해주어야 한다

또한, 마이너스 좌표에 접근 불가능하기 때문에 +1000을 해주어야 한다

좌표 변환 행렬

결국 변환 후 좌표의 범위는 0<=x,y<4000이 된다

좌표의 범위가 넓기 때문에 원소들은 배열에 저장해서 계속해서 이동시켜준다

처음에는 큐로 구현했다가 시간초과 나서 벡터로 변경했다

 

수도코드: 

for: 원소 벡터

    고유 이동 방향대로 이동

    if 좌표 범위를 벗어났다면 :

          해당 원소 삭제

    맵 위치에 카운트++

for: 원소 벡터

    if 맵 위치의 카운트 > 1(원소가 해당 좌표에 2개 이상) : 

           ans += 해당 원소의 에너지

             해당 원소 삭제

    맵 위치의 카운트 초기화

 

벡터를 활용할 수 있는 문제였다

iterator를 활용한 위치는 segment fault가 발생할 수 있으니 조심할 것 !!

 

소스코드:

#include <cstdio>
#include <queue>
#define max 4000
using namespace std;
typedef struct {
	int x, y;
}point;
typedef struct {
	point p;
	int d, e;
}atom;
vector<atom> v;
queue<point> c;
int tc, ans, n, dx[] = {0,0,-1,1}, dy[] = {1,-1,0,0};
int map[max][max];
bool safe(int x, int y){return x >= 0 && x < max && y >= 0 && y < max;}
int main() {
	freopen("input.txt", "r", stdin);
	scanf("%d", &tc);
	for (int T = 1; T <= tc; T++) {
		ans = 0;
		scanf("%d", &n);
		for (int i = 0,x,y,d,e; i < n; i++) {
			scanf("%d%d%d%d", &x, &y, &d, &e);
			x = (x + 1000) * 2;
			y = (y + 1000) * 2;
			v.push_back({ {x,y},d,e });
		}
		vector<atom>::iterator it;

		for (int t = 0; t <= max; t++) {

			for (it = v.begin(); it != v.end();) {
				it->p.x += dx[it->d];
				it->p.y += dy[it->d];
				
				if (!safe(it->p.x, it->p.y)) {
					it=v.erase(it);
					continue;
				}
				map[it->p.y][it->p.x]++;
				it++;
			}
			for (it = v.begin(); it != v.end();) {
				if (map[it->p.y][it->p.x]>1) {
					ans += it->e;
					c.push(it->p);
					it=v.erase(it);
					continue;
				}
				map[it->p.y][it->p.x]=0;
				it++;
			}
			while (!c.empty()) {
				map[c.front().y][c.front().x] = 0;
				c.pop();
			}
		}

		printf("#%d %d\n", T, ans);
		v.clear();
	}
	return 0;
}