SWEA5648

23 Jan 2020 • ProblemSolving

원자소멸시뮬레이션

문제출처

1.설계(30분)

  • 문제 해석

    • 원자들은 2차원 평면에서 이동하며 두개 이상의 원자가 충돌할 경우, 각자 보유한 에너지를 모두 방출하고 소멸합니다.
    • 최초위치 x,y, 이동방향을 가지고 있고, 이동속도는 모두 1초에 1칸씩 동시에 이동합니다.
    • 원자들이 소멸되면서 방출하는 에너지의 합을 구하는 문제입니다.
    • 1 <= N <= 1000, 1 <= K <= 100, -1000 <= x,y <= 1000

  • 설계

    • 원자 간 거리가 홀수일 경우에 충돌이 가능하게 좌표를 두배로 늘려야 합니다.
    • check배열에 에너지를 합한 후, 각 원소들의 에너지와 비교해서 원소 충돌의 유무를 판단하였습니다. 해당 방법을 효과적으로 구현하는 방법을 생각하는데 시간이 오래 걸렸습니다.
    • 각 원소를 벡터에 추가하여 시뮬레이션을 진행하고, 충돌된 원소를 지우는 작업을 합니다.

2.구현(45분)

  • 코드
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#define MAXN 4004
using namespace std;

int map[MAXN][MAXN];
struct node {
	int x;
	int y;
	int dir;
	int energy;
};
int N;
vector<node> v;

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int bfs() {
	int sum = 0;
	while (!v.empty()) {
		
		for (int i = 0; i < v.size(); i++) {
			int x = v[i].x;
			int y = v[i].y;
			int energy = v[i].energy;
			int dir = v[i].dir;
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			map[x][y] = 0;
			if (nx < 0 || ny < 0 || nx >= MAXN || ny >= MAXN) {
				v.erase(v.begin() + i);
				i--;
				continue;
			}
			map[nx][ny] += energy;
			v[i].x = nx;
			v[i].y = ny;
		}
		vector<pair<int,int> > tmp;
		for (int i = 0; i < v.size(); i++) {
			if (map[v[i].x][v[i].y] != v[i].energy) {
				tmp.push_back({ v[i].x,v[i].y });
				sum += v[i].energy;
				v.erase(v.begin() + i);
				i--;
			}
		}
		for (int i = 0; i < tmp.size(); i++) {
			map[tmp[i].first][tmp[i].second] = 0;
		}
	}
	
	return sum;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	for (int test_case = 1; test_case <= t; test_case++) {
		v.clear();
		cin >> N;
		for (int i = 0; i < N; i++) {
			int x, y, dir, energy;
			cin >> x >> y >> dir >> energy;

			v.push_back({ MAXN / 2 - 2 * y,MAXN / 2 + 2 * x,dir,energy });
		}
		cout << "#"<<test_case<<" "<<bfs() << "\n";
	}
	
	
	
	return 0;
}

  • 디버깅

  • 제출결과

    1916ms

3.마무리

  • 원소 충돌 유무를 판단하는데에 필요한 효율적인 자료 구조 및 방법을 생각하는데 오래 걸렸습니다. 실행속도를 보니 최적화가 잘 안된 것 같습니다. 다른 분들의 코드로 보았을 때, 각 원소들을 한칸씩 움직이지 않고 충돌이 발생하는 원소들을 찾아내는 방법을 따로 구현한 것 같습니다.
 SWEA

Related Posts