[SWEA] 5648. 원자 소멸 시뮬레이션

풀이

• 원자들의 처음 위치는 (-1000 <= x,y <= 1000)이면서 방향은 바뀌지 않으므로 해당 범위를 벗어난다면 곧 다른 원소들과 만나지 못함을 의미한다. 가능한 최대 map[][] 범위 => 2000 + 1
• 1초마다 1칸씩 이동하는데 바로 인접해서 위치한 경우, 0.5초가 지나면 만나서 소멸한다. 따라서 0.5초인 경우도 고려해야하므로 범위를 2배 늘려서 잡는다. 가능한 최대 map[][] 범위 => 2000 * 2 + 1 = 4001
• 이차원평면을 이차원배열로 바꿔야한다. 이차원 평면의 x, y좌표는 각각 배열의 column과 row에 대응된다. 또한 row는 이차원 평면과 달리, 맨 위에서부터 0으로 시작하므로 전체 길이(4001)를 뺀 다음 절대값을 씌어준다.
• map에 에너지를 기록하고 최대값(행,열)만큼 반복하면서 bfs 탐색을 한다. 동일 depth끼리 구분해서 이동해야하기 때문에 큐size만큼 큐에서 빼면서 이동하는데, map 기존 위치에서 에너지만큼 빼고 다음 위치에 에너지만큼 더해준다. 그리고 atom의 위치를 다음 위치로 바꿔주고 큐에 다시 넣는다.
• 다음 0.5초에서 큐를 빼낼 때, 해당 에너지 위치의 map값과 해당 원소의 에너지값과 다르다면, 원소 충돌이 일어난 것이기 때문에 해당 map값은 0으로 변경하고 해당 에너지는 answer에 더해주고 continue한다.
  ⭐⭐ 여기서 큐의 순서와 관계없이 map의 값을 바로 0으로 초기화 할 수 있는 이유: 0.5초를 기준으로 맵의 두 배 크기를 늘렸기 때문에, 같은 방향을 같는 연속적인 원소들로 초기값이 주어지더라도 원소들 사이가 한 칸씩 띄어지게 된다. 따라서 큐에서 poll되는 순서로 인해서 이동하는 방향에서 더 뒤에 있는 값이 먼저 나와서 move하더라도 0이 되는 map위치의 값에 전혀 영향을 주지 않는다.
• 🤔 각 테스트케이스마다 전역 map과 Queue를 초기화해주었는데 시간초과가 났다. 각 테케마다 map의 모든 원소는 0으로 변경되고 큐도 비어지기 때문에 초기화 코드를 빼주자 PASS했다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Solution_5648_원자소멸시뮬레이션{
	static class Atom{
		int c, r, energy, dir;
		public Atom(int c, int r, int dir,int energy) {
			this.c = c;
			this.r = r;
			this.dir = dir;
			this.energy = energy;
		}
	}
	private static Queue<Atom> q = new LinkedList<>();
	private static int[][] map=new int[4001][4001];; 
	private static int[] dr = {-1, 1, 0, 0};
	private static int[] dc = {0, 0, -1, 1};
	private static int ans;
	private static int mC;
	private static int mR;
	private static int mLength;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(input.readLine());
		for(int tc = 1; tc <= T; tc++) {
			int N = Integer.parseInt(input.readLine()); 
			ans = 0;
			mC = Integer.MIN_VALUE;
			mR =Integer.MIN_VALUE;
			for(int i= 0; i < N;i++) {
				StringTokenizer st = new StringTokenizer(input.readLine());
				int c = Integer.parseInt(st.nextToken())*2+2000; //x좌표값
				int r = Integer.parseInt(st.nextToken())*2+2000; //y좌표값
				r = Math.abs(r-4000);
				mC = Math.max(mC, c);
				mR = Math.max(mR, r);
				Atom atom = new Atom(c, r, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
				map[atom.r][atom.c] = atom.energy;
				q.add(atom);
			}
			mLength = Math.max(mC, mR);
			bfs();
			System.out.println("#" + tc + " " + ans);
		}//end of tc
	}

	private static void bfs() {
		while(mLength-- > 0) {
			int size = q.size();
			for(int i = 0; i < size; i++) {
				Atom atom = q.poll();
				if(map[atom.r][atom.c] != atom.energy) {
					map[atom.r][atom.c] = 0;
					ans += atom.energy;
					continue;
				}
				int nr = atom.r + dr[atom.dir];
				int nc = atom.c + dc[atom.dir];
				move(nr, nc, atom);
				
			}//end of depth
		}
	}

	private static void move(int nr, int nc, Atom atom) {
		map[atom.r][atom.c] -= atom.energy;
		if(isIn(nr, nc)) {
			map[nr][nc] += atom.energy; 
			atom.r = nr;
			atom.c = nc; 
			q.add(atom);
		}
	}

	private static boolean isIn(int nr, int nc) {
		if(nr < 0 || nr > mR || nc < 0 || nc > mC) return false;
		return true;
	}
}