[SW Expert Academy] 5648. 원자 소멸 시뮬레이션 C/C++ 풀이

또뮬레이션 문제

저번 문제를 나름 잘풀었다고 생각했고, 그에 비하면 방향 전환도 없는 개꿀문제라고 생각했다가 큰 코 다친 문제.

우선 이번 문제를 풀면서 느낀 것은

벡터는 정적 배열에 비해서 연산 속도가 엄청나게 느리다.

로직은 거의 똑같이 적은 두 코드를 비교하자면

 

#include <cstdio>
#include <vector>
#include <utility>

using namespace std;

FILE* in = stdin;

//원자의 상태를 저장하는 struct
struct mole_info {
	int x;
	int y;
	int dir;
	int e;
};

int t, n;
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };
// 폭발해서 모인 에너지를 저장해놓음
int delay[4001][4001];

int bomb(vector<mole_info>& mole) {
	int energy = 0;
    //mole 벡터가 비어있지 않다면 진행
	while (!mole.empty()) {
		for (int i = 0; i < mole.size(); i++) {
        	//delay 평면에 기존 x, y 값에 에너지 값을 없애줌
			delay[mole[i].x][mole[i].y] = 0;
            //위치 갱신
			mole[i].x += dx[mole[i].dir];
			mole[i].y += dy[mole[i].dir];
            //만약 범위를 벗어나지 않았다면 새로운 x,y 평면에 에너지 값 더해주기
			if(mole[i].x >= 0 && mole[i].x <= 4000 && mole[i].y >= 0 && mole[i].y <= 4000)
				delay[mole[i].x][mole[i].y] += mole[i].e;
		}
        //벡터 값 갱신을 위한 새 벡터에 기존 값을 그대로 옮겨준다.
		vector<mole_info> tmp_vector;
		tmp_vector.assign(mole.begin(), mole.end());
		mole.clear();
		for (int i = 0; i < tmp_vector.size(); i++)
		{
        	//원자의 위치가 좌표평면 범위 안에 있고
			if (tmp_vector[i].x >= 0 && tmp_vector[i].x <= 4000 && tmp_vector[i].y >= 0 && tmp_vector[i].y <= 4000)
			{
            	// delay 평면의 값과 에너지 값이 같다면 새 벡터에 넣어줌
				if (delay[tmp_vector[i].x][tmp_vector[i].y] == tmp_vector[i].e)
				{
					mole.push_back(tmp_vector[i]);
				}
                // 만약 값이 차이가 나고, 그 값이 0이 아니라면 해당 평면에 여러 에너지 값이 더해졌다는 뜻
				else if(delay[tmp_vector[i].x][tmp_vector[i].y] != 0)
				{
                	//폭발 에너지의 총합에 그 값을 더해줌
					energy += delay[tmp_vector[i].x][tmp_vector[i].y];
                    //해당 평면은 0으로
					delay[tmp_vector[i].x][tmp_vector[i].y] = 0;
				}
			}
		}
	}
	return energy;
}

int main() {
	fscanf(in, "%d", &t);
	for (int i = 0; i < t; i++)
	{
		fscanf(in, "%d", &n);
		vector<mole_info> mole;
		for (int j = 0; j < n; j++)
		{
			mole_info tmp;
			fscanf(in, "%d %d %d %d", &tmp.x, &tmp.y, &tmp.dir, &tmp.e);
            //직선으로 만날 경우 0.5 단위에서 만날 수 있으므로 2를 곱해줌
            //그리고 -1000 ~ 1000 범위 안이기 때문에 1000을 더해서 모두 양수로 바꾸어줌
			tmp.x = (tmp.x * 2 + 2000);
			tmp.y = (tmp.y * 2 + 2000);
			mole.push_back(tmp);
		}
		printf("#%d %d\n",i+1 ,bomb(mole));
	}
}

벡터를 이용한 해당 코드는 시간초과가 났다...

 

Dummy 문제에서 큐와 덱으로 재미를 봤던터라 벡터를 사용하는 연습을 하고 있었는데 시간 절약을 위해선 정적 배열이 짱인 것을 느끼고 정적 배열으로 새로 짠 코드..

 

#include <cstdio>
#include <vector>
#include <utility>

using namespace std;

FILE* in = stdin;

struct mole_info {
	int x;
	int y;
	int dir;
	int e;
};

int t, n;
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };
int delay[4001][4001];

int bomb(int n, mole_info (&mole)[1001]) {
	int energy = 0;
	while(1==1)
	{
    	// 없는 원소가 몇 개인지 판별하기 위한 변수
		int non_exist = 0;
		for (int i = 0; i < n; i++) {
        	//벡터와 달리 없어진 원자를 따로 없애주지 않기 때문에 에너지 값을 0으로 바꾸어서
            //없어진 원소를 트래킹
			if (mole[i].x < 0 || mole[i].x > 4000 || mole[i].y < 0 || mole[i].y > 4000 || mole[i].e == 0)
			{
				non_exist++;
				continue;
			}
			delay[mole[i].x][mole[i].y] = 0;
			mole[i].x += dx[mole[i].dir];
			mole[i].y += dy[mole[i].dir];
			if (mole[i].x >= 0 && mole[i].x <= 4000 && mole[i].y >= 0 && mole[i].y <= 4000)
				delay[mole[i].x][mole[i].y] += mole[i].e;
		}
        //없어진 원소가 n개면 끝
		if (non_exist == n)
			break;
		for (int i = 0; i < n; i++)
		{
			if (mole[i].x >= 0 && mole[i].x <= 4000 && mole[i].y >= 0 && mole[i].y <= 4000 && mole[i].e != 0)
			{
				if (delay[mole[i].x][mole[i].y] != mole[i].e)
				{
					energy += delay[mole[i].x][mole[i].y];
					delay[mole[i].x][mole[i].y] = 0;
					mole[i].e = 0;
				}
			}
		}
	}
	return energy;
}

int main() {
	fscanf(in, "%d", &t);
	for (int i = 0; i < t; i++)
	{
		fscanf(in, "%d", &n);
		mole_info mole[1001];
		for (int j = 0; j < n; j++)
		{
			mole_info tmp;
			fscanf(in, "%d %d %d %d", &tmp.x, &tmp.y, &tmp.dir, &tmp.e);
			tmp.x = (tmp.x * 2 + 2000);
			tmp.y = (tmp.y * 2 + 2000);
			mole[j] = tmp;
		}
		printf("#%d %d\n", i + 1, bomb(n, mole));
	}
	return 0;
}

없어진 원소를 에너지 값 0으로 보내는 것을 제외하고는 똑같은 로직을 가지고 있다.

하지만 처리속도가 깡패..

 

<p.s.>

 

처음에는 while이 아닌 for(int time = 0; time < 4000; time++)으로 bomb 함수를 구현했는데 47개 정답으로 나왔다. 왜 그런가했더니 총 4001번의 이동이 가능함. -1000 에서 1000까지... 범위를 제대로 판단하도록 하자. 이것때문에 한 시간 날린건 안비밀....