[모의 SW 역량테스트] 원자 소멸 시뮬레이션 (C++)

원자들이 충돌할 경우 가지고 있는 에니저를 발산한 뒤 소멸하는 시뮬레이션 문제입니다. 원자가 1초에 1만큼 이동하지만 0.5초에 충돌할 수 있어 전체 격자를 2배로 늘려 계산해야 합니다. 

 

C++을 사용할 경우 vector<vector<int>>와 같은 2차원 벡터를 사용할 수 있는데 int[][]보다 랜덤접근이 느려 TLE가 발생합니다. 원자를 저장하는 atoms 배열과 원자들의 수를 카운트하는 board, 원자들이 충돌했는지 확인하는 crash 모두 vector 구조를 사용하지 않았습니다. 아래 코드에서 위의 3개 중 하나라도 vector를 사용하면 TLE가 발생했습니다.

 

	#include <bits/stdc++.h>
	#define endl '\n'
	#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	using namespace std;
	typedef long long ll;
	typedef pair<int,int> pii;
	typedef pair<ll, ll> pll;
	typedef tuple<int,int,int> tiii;
	const int INF=1e9+1;
	int dx[]={0,0,-1,1}, dy[]={1,-1,0,0}; // U,D,L,R
	// vector로 접근하는 것이 int 배열로 접근하는 것보다 느림
	struct atom {
	int x, y;
	int dir;
	int K;
	bool death;
	} atoms[1001];
	int board[4001][4001];
	int crash[4001][4001];
	int alive_check(vector<int>& alive, int n) {
	// 살아있는 원자만 리턴
	int alive_cnt=0;
	for(int i=1,idx=0;i<=n;i++) {
	if(!atoms[i].death) {
	alive[idx++]=i, alive_cnt++;
	}
	}
	return alive_cnt;
	}
	int simul(vector<int>& alive, int alive_cnt) {
	// 살아있는 원자들에 대해 시뮬레이션
	for(int i=0;i<alive_cnt;i++) {
	// 원자 이동
	int n=alive[i];
	auto& [x,y,d,k,death]=atoms[n];
	board[x][y]--;
	int nx=x+dx[d], ny=y+dy[d];
	if(nx<0 || nx>=4000 || ny<0 || ny>=4000) {
	death=1;
	continue;
	}
	x=nx, y=ny;
	board[nx][ny]++;
	// 원자가 한 격자내에 여러개 존재할 경우 충돌
	if(board[nx][ny]>1) crash[nx][ny]=1;
	}
	// 충돌하는 원자들에 대해 에너지 합산, 원자 죽음
	int j=0;
	for(int i=0;i<alive_cnt;i++) {
	int n=alive[i];
	auto& [x,y,d,k,death]=atoms[n];
	if(crash[x][y]) {
	board[x][y]--;
	j+=k;
	death=1;
	if(board[x][y]==0) crash[x][y]=0;
	}
	}
	return j;
	}
	int solve() {
	int n; cin>>n;
	memset(board,0,sizeof(board));
	memset(crash,0,sizeof(crash));
	for(int i=1;i<=n;i++) {
	int x,y,d,k; cin>>x>>y>>d>>k;
	x=(x+1000)*2, y=(y+1000)*2;
	atoms[i]={x,y,d,k,0};
	board[x][y]++;
	}
	int r=0, k=4002;
	vector<int> alive(1001);
	while(k--) {
	int cnt=alive_check(alive,n);
	// 살아있는 원자가 없으면 종료
	if(!cnt) break;
	r+=simul(alive,cnt);
	}
	return r;
	}
	int main() {
	fastio
	int t; cin>>t;
	for(int tc=1;tc<=t;tc++) {
	cout<<"#"<<tc<<' '<<solve()<<endl;
	}
	return 0;
	}

view raw swea_atom_collide_simulation.cpp hosted with ❤ by GitHub