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

SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기)

 

삼성 A형 전체 링크

 

모의 SW 역량테스트 문제집

 

원자 소멸 시뮬레이션 링크

 

이후 설명 및 입/출력은 링크 참고

 

좌표가 -1000 ~ 1000으로 굉장히 넓기 때문에, MAP에는 atom을 표시만 하고,

atom 배열을 이용해 atom을 이동한다.

atom 구조체는 좌표 (r, c), 방향, 보유 에너지가 필요하다.

typedef struct st
{
	int r;
	int c;
	int dir;
	int energy;
}ATOM;

ATOM atom[1000 + 100];

 

좌표가 음의 값을 가지므로, OFFSET을 이용하여 양의 값으로 만들어야 배열에 담을 수 있다.

이 때, 0.5초 구간 충돌을 구현하기 위해, 좌표를 2배로 늘린다.

좌표를 2배로 늘렸으니 원자들은 항상 1초마다 충돌한다.

가장 작은 좌표의 값은 -1000이고 2배를 할 경우 -2000이 되므로 OFFSET으로 2000을 모든 좌표에 더한다.

그리고 MAP에는 energy를 누적한다. 따라서 초기에는 자신의 energy가 저장되어있다.

#define MAX (4000 + 100)
#define OFFSET (2000)

void input()
{
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		int r, c, dir, energy;

		scanf("%d %d %d %d", &c, &r, &dir, &energy);

		r = r * 2 + OFFSET;
		c = c * 2 + OFFSET;

		atom[i].r = r;
		atom[i].c = c;
		atom[i].dir = dir;
		atom[i].energy = energy;
		
		MAP[r][c] = energy;
	}
}

 

또한, 이 문제에서는 dr, dc의 배열의 값이 다른 문제와 다르다.

보통 dr, dc 배열에서 위 방향은 현재 row보다 1 작은 값을 의미하지만, 

현재는 배열이 아닌 수학적인 좌표를 사용하므로, 위 방향은 row보다 1 큰 값을 의미한다.

/* 순서대로 상, 하, 좌, 우 */
int dr[] = { 1, -1, 0, 0 };
int dc[] = { 0, 0, -1, 1 };

---

좌표가 매우 크기 때문에, atom이 충돌했는지 안 했는지 매번 check하면 time out이 난다.

따라서 충돌하지 않은 atom만 배열에 담아서 움직인다.

 

최초 simulate에서는 atom배열을 liveAtom으로 모두 옮긴다.

tcnt는 liveAtom에서 충돌하지 않은 atom만 따로 모으기 위해 사용하는 변수다.

sum은 충돌한 atom의 energy를 누적한다.

int simulate()
{
	ATOM liveAtom[1000 + 10] = { 0 };
	int lcnt, tcnt, sum;

	lcnt = sum = 0;

	for (int i = 0; i < N; i++) liveAtom[lcnt++] = atom[i];
    
	...
}

 

모든 liveAtom을 움직여보면서 충돌하는지 판단한다.

liveAtom의 다음 좌표 (nr, nc)는 현재 좌표와 dr, dc 배열을 이용해 구할 수 있다.

int nr, nc;

nr = liveAtom[i].r + dr[liveAtom[i].dir];
nc = liveAtom[i].c + dc[liveAtom[i].dir];

 

energy가 이동하기 때문에 현재 좌표는 0으로 만든다.

그리고 liveAtom의 좌표를 nr, nc로 갱신한다.

만약 MAP[nr][nc]가 0이라면, 빈 칸이라는 뜻이므로, tcnt를 이용하여 liveAtom 배열의 처음부터 저장한다.

MAP[nr][nc]가 0인 경우는 energy, 0이 아닌 경우는 energy를 추가해야하므로,

두 경우 모두 MAP[nr][nc] += liveAtom[i].energy가 된다.

 

MAP[liveAtom[i].r][liveAtom[i].c] = 0;

liveAtom[i].r = nr;
liveAtom[i].c = nc;

if (MAP[nr][nc] == 0) liveAtom[tcnt++] = liveAtom[i];

MAP[nr][nc] += liveAtom[i].energy;

 

하지만 위의 코드에 문제가 있다.

충돌하는 atom은 liveAtom에 다시 저장하지 않기로 하였으나,

최초로 MAP[nr][nc]에 들어온 atom은 liveAtom에 저장할 수 밖에 없다.

 

따라서 움직이기 전에 liveAtom의 energy와 MAP[r][c]의 energy가 같은지 비교할 필요가 있다.

if (liveAtom[i].energy != MAP[liveAtom[i].r][liveAtom[i].c])
{
	sum += MAP[liveAtom[i].r][liveAtom[i].c];
	MAP[liveAtom[i].r][liveAtom[i].c] = 0;

	continue;
}

 

다른 atom이 움직이면서 MAP[nr][nc]에 energy를 누적하였다.

liveAtom에 있는 좌표 (r, c)가 충돌이 발생한 좌표 (nr, nc)였다면,

MAP[r][c]에 저장된 energy는 자신의 energy와 다르게 된다.

 

따라서 이 경우에 MAP에 저장된 energy를 sum에 누적하고 MAP을 0으로 바꾼 뒤,

liveAtom에 들어가지 않도록 continue 처리한다.

 

위의 경우를 모두 고려하고, (nr, nc)의 좌표가 0 ~ 4000을 벗어나는 경우에도 continue 처리를 해주면 된다.

모든 atom이 충돌하거나 좌표를 넘어가게 되면 lcnt가 0이 되므로, break한다.

int simulate()
{
	ATOM liveAtom[1000 + 10] = { 0 };
	int lcnt, tcnt, sum;

	lcnt = sum = 0;

	for (int i = 0; i < N; i++) liveAtom[lcnt++] = atom[i];

	while (1)
	{
		tcnt = 0;
		for (int i = 0; i < lcnt; i++)
		{
			if (liveAtom[i].energy != MAP[liveAtom[i].r][liveAtom[i].c])
			{
				sum += MAP[liveAtom[i].r][liveAtom[i].c];
				MAP[liveAtom[i].r][liveAtom[i].c] = 0;

				continue;
			}

			int nr, nc;

			nr = liveAtom[i].r + dr[liveAtom[i].dir];
			nc = liveAtom[i].c + dc[liveAtom[i].dir];

			if (nr < 0 || nc < 0 || nr > 4000 || nc > 4000) continue;

			MAP[liveAtom[i].r][liveAtom[i].c] = 0;

			liveAtom[i].r = nr;
			liveAtom[i].c = nc;

			if (MAP[nr][nc] == 0) liveAtom[tcnt++] = liveAtom[i];

			MAP[nr][nc] += liveAtom[i].energy;
		}

		lcnt = tcnt;

		if (lcnt == 0) break;
	}

	return sum;
}

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (4000 + 100)
#define OFFSET (2000)

int T, N;
int MAP[MAX][MAX];

typedef struct st
{
	int r;
	int c;
	int dir;
	int energy;
}ATOM;

ATOM atom[1000 + 100];

void input()
{
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		int r, c, dir, energy;

		scanf("%d %d %d %d", &c, &r, &dir, &energy);

		r = r * 2 + OFFSET;
		c = c * 2 + OFFSET;

		atom[i].r = r;
		atom[i].c = c;
		atom[i].dir = dir;
		atom[i].energy = energy;
		
		MAP[r][c] = energy;
	}
}

/* 순서대로 상, 하, 좌, 우 */
int dr[] = { 1, -1, 0, 0 };
int dc[] = { 0, 0, -1, 1 };

int simulate()
{
	ATOM liveAtom[1000 + 10] = { 0 };
	int lcnt, tcnt, sum;

	lcnt = sum = 0;

	for (int i = 0; i < N; i++) liveAtom[lcnt++] = atom[i];

	while (1)
	{
		tcnt = 0;
		for (int i = 0; i < lcnt; i++)
		{
			if (liveAtom[i].energy != MAP[liveAtom[i].r][liveAtom[i].c])
			{
				sum += MAP[liveAtom[i].r][liveAtom[i].c];
				MAP[liveAtom[i].r][liveAtom[i].c] = 0;

				continue;
			}

			int nr, nc;

			nr = liveAtom[i].r + dr[liveAtom[i].dir];
			nc = liveAtom[i].c + dc[liveAtom[i].dir];

			if (nr < 0 || nc < 0 || nr > 4000 || nc > 4000) continue;

			MAP[liveAtom[i].r][liveAtom[i].c] = 0;

			liveAtom[i].r = nr;
			liveAtom[i].c = nc;

			if (MAP[nr][nc] == 0) liveAtom[tcnt++] = liveAtom[i];

			MAP[nr][nc] += liveAtom[i].energy;
		}

		lcnt = tcnt;

		if (lcnt == 0) break;
	}

	return sum;
}

int main(void)
{
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		printf("#%d %d\n", tc, simulate());
	}

	return 0;
}