[SW Expert Academy] 원자 소멸 시뮬레이션 - java

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

SW Expert Academy

public class 원자소멸2 {
	static List<Atom> atom;
	static int dx[] = new int[] { 0, 0, -1, 1 };
	static int dy[] = new int[] { 1, -1, 0, 0 };
	static int map[][] = new int[4001][4001];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		atom = new ArrayList<>();
		for (int tc = 1; tc <= T; tc++) {
			int N = Integer.parseInt(br.readLine());
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int x = (Integer.parseInt(st.nextToken()) + 1000) * 2;
				int y = (Integer.parseInt(st.nextToken()) + 1000) * 2;
				int dir = Integer.parseInt(st.nextToken());
				int energy = Integer.parseInt(st.nextToken());
				atom.add(new Atom(x,y,dir,energy));
				map[x][y] = energy;
			}

			// 상(y값 증가), 하(y값 감소), 좌(x값 감소) 우(x값 증가)
			int result = solve();
			System.out.println("#"+tc+" "+result);
		}
	}

	static int solve() {
		int sum = 0;
		while (!atom.isEmpty()) {
			for (int i = 0; i < atom.size(); i++) {
				Atom a = atom.get(i);
				map[a.x][a.y] = 0;
				a.x += dx[a.dir];
				a.y += dy[a.dir];
				if (a.x > 4000 || a.x < 0 || a.y > 4000 || a.y < 0) {
					atom.remove(i);
					i--;
					continue;
				}
				map[a.x][a.y] += a.energy;
			}
			for (int i = 0; i <atom.size(); i++) {
				Atom a = atom.get(i);
				if (map[a.x][a.y] != a.energy) {
					sum += map[a.x][a.y];
					map[a.x][a.y] = 0;
					atom.remove(i);
					i--;
				}
			}
		}
		return sum;
	}
	
	static class Atom {
		int x, y;
		int dir;
		int energy;

		public Atom(int x, int y, int dir, int energy) {
			this.x = x;
			this.y = y;
			this.dir = dir;
			this.energy = energy;
		}
	}
}

핵심은 0.5초 단위로 원자들이 충돌하는 것입니다.

그래서 원자의 위치들을 2배 늘려 0.5초 충돌을 처리하였습니다.

map[][]의 경우 

for문을 돌 때마다 new int[4001][4001]로 생성할 경우 메모리 초과로 런타임 에러가 발생합니다.

 

1. 원자들의 위치를 map에 할당합니다.

2. 원자들이 이동하면 이동된 map에 에너지값을 더해줍니다.

3. 모든 원자들을 이동 후 map의 에너지값이 해당 원자의 에너지값보다 큰 경우 충돌하였으므로

sum에 더해주고 해당 위치인 map에 0으로 초기화합니다. 그 다음 해당 원자를 삭제합니다.

4. 원자의 위치인 map의 에너지값이 0일 경우 충돌하였으므로 해당 원자를 삭제합니다.