SWEA - 5648 ) 원자소멸 시뮬레이션

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRFInKex8DFAUo

SW Expert Academy

---

 

원자들이 이동하면서 충돌하면 그 에너지의 누적합을 구하는 문제이다.

 

사실 구현자체는 어렵지 않았지만, 구현을 쉽게하려고 배열을 많이 쓴다던가, For문을 많이 돌리게되면 시간초과에 벽에

 

마주하게된다. 그렇다면 어떻게 시간초과를 줄일까?

 

1. 썼던 배열을 최대한 재사용하자

 

2. for문의 범위를 최대한으로 줄이고, 범위를 벗어나는 케이스에대해서 처리를 해주자.

 

3. Heap영역에 최소한으로 다가가자.

 

원자충돌 시뮬레이션을 풀기위한 알고리즘은 다음과같다.

 

처음입력으로 모든 원자들을 arraylist에 넣은뒤 하나씩 뽑아서 이동시킨후 그 이동시킨 곳에 map 2차원 배열에

 

에너지의 합을 기록하여 둔다. 이후, 이동이 끝나고 충돌을 검사할때에 원자하나가 가진 에너지 값보다

 

더 큰 값이 누적되어있다면, 다른 원자에너지가 더해진 것이므로 그 원자는 충돌되어 사라져야한다

 

( 리스트에서 삭제하고, index를 -1 해준다 )

 

그러면 4개의 원자가 한 곳에 충돌하였을때 3개는 자신보다 크니까 바로삭제되지만 마지막 한개의 원자는 자기의

 

값과 똑같은 값을 가지므로 삭제가 되지않는다. 

 

이를 해결하기위해 Boolean 2차원 배열로 메모리를 최소로 잡고, 충돌이 일어난곳이라는 표시를 해준다.

 

즉 원자의 에너지가 1인 원자 4개가 충돌되어 map에 4란값이 있고, 리스트에서 해당 좌표를 꺼내왔을 때에,

 

1보다 큰 4값이 있기때문에 boolean 값을 바꾸어주고 3으로 에너지를 answer에 누적시키고,

 

그다음에 해당 좌표로 갔다면 또 -1해주고 반복한다.

 

최종적으로 map이 0 이된다면 그 좌표에 해당하는 원자들의 값이 모두 sum에 더해진것이므로 boolean배열을 원래로

 

되돌린다. 

 

처음에 에너지를저장하는 배열, 충돌을 확인하는 배열을 한 step마다 잡아주었는데 터진것을 보아

 

이런식으로 풀으라는 것 같다.

---

 

package practice;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class 원자충돌시뮬레이션 {
	static int dx[] = {1,-1,0,0};
	static int dy[] = {0,0,-1,1};
	static int map[][] = new int[4001][4001];
	static boolean visit[][] = new boolean[4001][4001];
	static int answer = 0;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(st.nextToken());
		for(int tc = 1 ; tc <= T ; tc++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			ArrayList<int []> atom = new ArrayList<>();
			for(int index = 0 ; index < n ; index++) {
				st = new StringTokenizer(br.readLine());
				int y = Integer.parseInt(st.nextToken())*2 +2000;
				int x = Integer.parseInt(st.nextToken())*2 +2000;
				int dir = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());
				map[y][x] = e; 
				atom.add(new int[] {y,x,dir,e});
			}
			while(atom.size() != 0) {
				for(int index = 0 ; index < atom.size() ; index++) {
					int y = atom.get(index)[0];
					int x = atom.get(index)[1];
					map[y][x] = 0;
					atom.get(index)[0] += dy[atom.get(index)[2]];
					atom.get(index)[1] += dx[atom.get(index)[2]];
					 y = atom.get(index)[0];
					 x = atom.get(index)[1];
					if(y >=0 && x>= 0 && y < 4001 && x < 4001 ) {
						map[y][x] += atom.get(index)[3];
					}
					else {
						atom.remove(index);
						index--;
					}
				}
				
				
				for(int index = 0 ; index < atom.size() ; index++) {
					int y = atom.get(index)[0];
					int x = atom.get(index)[1];
					if(visit[y][x]) {
						map[y][x] -= atom.get(index)[3];
						answer += atom.get(index)[3];
						atom.remove(index);
						index--;
						if(map[y][x] == 0) {
							/
							visit[y][x] = false;
						}
					}
					else if(map[y][x] > atom.get(index)[3] && !visit[y][x]){ 
						visit[y][x] = true;
						map[y][x] -= atom.get(index)[3];
						answer += atom.get(index)[3];
						atom.remove(index);
						index--;
						
					}
				}
			}
			sb.append("#"+tc+" "+answer+"\n");
			answer =0;
		}
		System.out.print(sb);
	}

}

---