[SWEA 5648번] 원자소멸 시뮬레이션 :: 늦깎이 IT

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

SWEA 모의역량 테스트 문제들 중에서 시뮬레이션 문제로는 끝판왕인 것 같다.

입력으로 주어지는 원자들의 초기 입력 값들도 음수로 주어지고, 원자 충돌이 1초, 2초가 아닌 1.5초, 2.5초처럼

소수점으로도 충돌한다. 이 입력 값을 연산이 편하게 바꿔주는 것이 중요하다.

※ 런타임에러가 계속 뜨길래, 도대체 왜그런가 했더니 visited 배열과 collapse 배열을 tCase마다 새롭게 초기화

했더니 메모리가 부족해서 그랬다.

[풀이 방법]

1. 입력으로 주어지는 원자의 좌표 값은 -1000 이상 1000이하이므로, 이를 양수 좌표로 바꿔줘야 한다.

입력된 좌표 각각에 +1000을 해줌으로써 0이상 2000이하로 범위를 바꾼다. 

2. 0.5초 단위로 원자들이 충돌할 수 있으므로, 각 좌표에 x2를 해주게되면, 0.5초 단위로 충돌하는 것이 아니라

원자들이 1초 단위로 충돌할 수 있게 된다. 그러므로 2차원 배열의 총 길이는 최소 4000으로 지정해야 한다.

단, 이렇게되면 입력으로 받은것과 상하가 뒤바뀌기 때문에, 이동방향에 따른 감소값도 상, 하 방향은 조정해야한다

3. 원자들의 위치, 방향, 에너지를 저장할 수 있는 Node 클래스를 생성한다. 그리고 입력받는 원자의 갯수만큼

Node 배열을 선언하여 저장한다.

4. int형 2차원 배열인 visited 배열을 선언하고, 이 배열에서 원자들의 움직임을 표시한다. 해당 위치에는 원자가 존재하는 수 만큼 저장한다. 그 이유는 모든 원자를 한칸씩 이동했을 때, 어느 임의의 위치의 값이 2이상이면 같은 위치에 원자가 2개이상 존재한다는 뜻이다. 원자가 2개 이상 똑같은 위치에 존재한다는 것은 충돌이 발생했다는 뜻이므로 collapse 배열을 true로 변경한다.

5. 원자들을 저장하고 있는 Node 배열을 순회하면서 충돌이 발생했다면 원자를 소멸시켜야 한다. 해당 원자의 위치에서 collapse 배열 값이 true라면, 충돌이 발생했다는 뜻이므로 해당 원자를 소멸시키고 해당 자리의 visited 값도 1 감소시킨다. 이때 collapse가 true이면서, visited도 1인 경우는 충돌이 발생한 위치에서 마지막 원소값을 제거해주기 직전이므로, collapse 값을 false로 바꿔줘야만 한다.

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int tCase, N, MAX = 4001;
    static int[][] visited;
    static boolean[][] collapse;
    static Node[] atoms;
    static int[] dirX = new int[] { 1, -1, 0, 0 };
    static int[] dirY = new int[] { 0, 0, -1, 1 };
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        tCase = Integer.parseInt(br.readLine());
        collapse = new boolean[MAX][MAX];
        visited = new int[MAX][MAX];
        
        for (int t = 1; t <= tCase; t++) {
 
            N = Integer.parseInt(br.readLine());
 
            atoms = new Node[N];
 
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                int col = Integer.parseInt(st.nextToken());
                int row = Integer.parseInt(st.nextToken());
                int dir = Integer.parseInt(st.nextToken());
                int power = Integer.parseInt(st.nextToken());
                atoms[i] = new Node((row + 1000) * 2, (col + 1000) * 2, dir, power);
                visited[atoms[i].row][atoms[i].col] = 1;
            }
            int ans = solve();
            System.out.println("#" + t + " " + ans);
        }
    }
 
    public static int solve() {
 
        int numOfAtom = N;
        int ans = 0;
 
        for (int j = 0; j < MAX + 5; j++) {
            // 원자들을 이동시킴
            for (int i = 0; i < numOfAtom; i++) {
 
                // 이동시키기 전
                int row = atoms[i].row;
                int col = atoms[i].col;
                int dir = atoms[i].dir;
                visited[row][col] -= 1;
 
                // 이동시키기
                if (isBoundary(row + dirX[dir], col + dirY[dir])) {
                    row += dirX[dir];
                    col += dirY[dir];
                    atoms[i].row = row;
                    atoms[i].col = col;
                    visited[row][col] += 1;
 
                    if (visited[row][col] >= 2)
                        collapse[row][col] = true;
 
                } else {
                    // 좌표를 벗어나는 원자들을 제거한다.
                    atoms[i] = atoms[numOfAtom - 1];
                    numOfAtom--;
                    i--;
                }
            }
 
            // 원자들의 충돌여부 확인
            for (int i = 0; i < numOfAtom; i++) {
 
                int row = atoms[i].row;
                int col = atoms[i].col;
 
                if (collapse[row][col] == true) {
 
                    if (visited[row][col] == 1)
                        collapse[row][col] = false;
 
                    ans += atoms[i].power;
                    visited[row][col] -= 1;
                    atoms[i] = atoms[numOfAtom - 1];
                    numOfAtom--;
                    i--;
                }
            }
            if (numOfAtom == 0)
                break;
        }
        return ans;
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < MAX) && (col >= 0 && col < MAX);
    }
}
 
class Node {
    int row;
    int col;
    int dir;
    int power;
 
    public Node(int row, int col, int dir, int power) {
        this.row = row;
        this.col = col;
        this.dir = dir;
        this.power = power;
    }
 
}