SW EXPERT 5648 원자 소멸 시뮬레이션 C 풀이 - 시뮬레이션

악명 높은 삼성 기출문제이다.

시간 단위가 0.5초 (가는 길에 서로 마주보는 다른 원자와 충돌하는 경우) 이기 때문에 상당히 어려운 문제다.

사실 겁나 어렵다.

더 밑의 차수를 보면 메모리 초과도 있다.

 

조건은1<= N<=1000, -1000<=x,y<=1000, 1<=k<=100, 충돌시 완전히 사라짐, 방향은 절대 안바뀐다.

 

접근 방식은 다음과 같다.

1. 원자는 범위 밖에 존재하지 않으므로 충돌은 주어진 범위(-1000~1000)에서만 일어난다.

2. 범위 끝에서 끝으로 가는 경우가 존재하므로 최소 2천 초의 시뮬레이션이 필요하다.

3. 2임에도 불구하고 원자가 단 1개만 남아있을 경우는 절대 충돌이 불가능하므로 종료해도 무관하다.

4. 0.5s 단위의 충돌은 서로 마주보고 오는 경우에만 가능하고, 제 3자가 낄 수 없고 원자의 방향이 바뀌지 않으므로 유일하다.

5. 1s 단위의 충돌은 동시에 여러 원자(최대 4개)가 가능하다.

 

시도해본 방식은 다음과 같다.

1. n개의 원자의 정보를 받아 특정 원자와 다른 원자를 직접 비교하여 충돌 여부를 판단하여 에너지를 구한다.

-> 최대 n^2 * 2000s 의 경우가 필요하므로 10^9 이 필요하다. 당연히 실패.

 

2. map에 현재 정보를 그려놓고 이동시켜본다.

-> 0.5초 단위의 충돌과 1초 단위의 충돌을 구분하기가 매우 어렵다.

예를 들어 (0,1,2,3) 이 (상,하,좌,우)일 때

0 1

3 3 2 

인 경우를 판단해보면, 3과 2가 마주보고 있는 경우를 먼저 진행할 때는 상관없지만, 1,3 을 먼저 진행할 경우

3 이 있는 위치에서의 판단은 굉장히 힘들다. (이걸로 2시간 소요, 추가 맵을 사용하다가 실패)

 

3. 사건이 0.5초 단위로 일어나기 때문에 공간으로 치환하여 생각하면 1초에 1칸을 0.5초에 1칸으로 바꿔 1초에 2칸을 움직이는 개념을 생각한다. -> 시험이었으면 여기까지 오는데 시험시간 다 썼을 듯

 

3번으로 통과할 수 있었고 해결 방식은 다음과 같다.

1. 입력 받을 때 offset을 1000으로 주어 음수 값을 양수 혹은 0으로 치환시키고, 거리를 2배 시켜준다.

2. 정해진 시간(2000초 -> 4000 회)만큼 반복하며 시뮬레이션을 돌린다.

3. 고려해야할 원자와 아닌 입자를 구분하여 돌리고, 맵에 충돌이 가능한지 여부를 기록하여 사용한다.

4. 이동할 때는 반드시 있었던 자리를 지워준다.

 

이 4단계만 거치면 다른 문제와 비슷하다. 맵을 2배 늘리는 것을 생각하지 못했다면 한 이틀 걸렸을 것 같다.

 

주의할 점은 다음과 같다.

1. 반드시!! 원래 있었던 자리를 맵에서 지워준다.

2. 좌표를 제대로 치환시켜야한다. 1000을 더하고 2배를 하자. (2배하고 2천 더해도 되나)

3. 위 방향이 y+1이다. 

4. 충돌했다면, 충돌한 모든 원자의 에너지를 0으로 바꿔주고, 맵에서도 지워주되 같은 시간동안은 영향력을 미쳐야한다.(3개가 충돌해야하는데 2개만 충돌할 경우 발생)

 

전체코드

0
#include <stdio.h>
#include <string.h>

//맵밖으로나가면 의미없음
int t, n;
int dy[] = { 1,-1,0,0 };//상하좌우
int dx[] = { 0,0,-1,1 };
typedef struct st {
	int y, x, dir, K;
}AT;
AT at[1002];

int map[4001+10][4001+10];

int solve() {
	int ret = 0;
	int time = 4001;//맵 끝(-1000 or 1000) 에서 다른 끝으로 이동하는데 걸리는 시간
	int num = 0;//원자 1개 이하로 남으면 더이상진행필요없음
	memset(map, 0, sizeof(map));//필수
	while (time--) {
		num = 0;
		for (int i = 1; i <= n; i++) {
			//범위 밖을 나가면 반대편에서 오는 원자가 없기 때문에 충돌 x 고려 x
			if (at[i].y > 4000 || at[i].y < 0 || at[i].x >4000 || at[i].x < 0) continue;
			//원래 있던 자리 클리어
			map[at[i].y][at[i].x] = 0;
			//이미 충돌한 애라면 고려 x
			if (at[i].K == 0) continue;

			//다음 장소
			int ny = at[i].y + dy[at[i].dir];
			int nx = at[i].x + dx[at[i].dir];
			//다음 장소가 범위 밖이면 위치 갱신해주고 고려x
			if (ny > 4000 || ny < 0 || nx>4000 || nx < 0) {
				at[i].y = ny;
				at[i].x = nx;
				continue;
			}
			//움직일 수 있는 원자 +1
			num++;

			//만약 어떤 원자가 먼저 왔었다면
			if (map[ny][nx]) {
				//먼저 온 원자 에너지 +
				ret+=at[map[ny][nx]].K;
				//방금 도착한 원자 에너지 +
				ret += at[i].K;
				//먼저 온 원자 에너지 0 (충돌 끝)
				at[map[ny][nx]].K = 0;
				//방금 도착한 원자에너지 0
				at[i].K = 0;
				//혹시 모르니 위치 갱신
				at[i].y = ny;
				at[i].x = nx;
			}//내가 가장 먼저 도착했거나 아무도 오지 않을 경우
			else {
				//내 인덱스를 남김
				map[ny][nx] = i;
				//위치 갱신
				at[i].y = ny;
				at[i].x = nx;
			}
			
		}
		//원자 1개 이하
		if (num <= 1) break;
	}
	return ret;
}

int main() {
	scanf("%d", &t);
	for (int loop = 1; loop <= t; loop++) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%d %d %d %d", &at[i].x, &at[i].y, &at[i].dir, &at[i].K);
			//좌표 -1000 -> 0 으로 offset 설정
			at[i].y += 1000;
			at[i].x += 1000;
			// 0.5초단위 움직임
			at[i].y *= 2;
			at[i].x *= 2;
		}
		int ans = solve();
		printf("#%d %d\n", loop, ans);
	}
	return 0;
}