[SW Expert] 5648. [모의 SW 역량테스트] 원자 소멸 시뮬레이션

생각

원자들이 있고, 각 원자들은 상 하 좌 우 중 한 방향으로만 전진을 한다.
각각의 원자들이 가지고 있는 에너지를 K 라 할 때, 둘 이상의 원자가 부딪히면 그 원자들의 K 값이 방출된다.
이 때, 방출된 K 값의 총합을 구하여라.

풀이후 생각

어마어마 한 문제였다. 사진 한 장이 말을 대신해 준다.

제출이 17차지 머가 잘못됐는지를 찾기위해 질문도 올렸었다. 답변해주신 분들에게 감사합니다!

결론부터 살펴보면 너무 어렵게 생각했다가 맞는 표현인 것 같다. 하지만 한 생각에 사로잡히면... 잠시 다른건 보이지 않는다는걸 이번에도 느끼게 되었다. 그래도 오류를 찾아서 PASS 시키면 묘하게 이맛에 문제푸나? 생각이 들기도 한다.

▶ 우선 K=0인 값이 존재해서 오류 제보를 했다.

처음 생각

좌표 평면이 마이너스 값으로 주어져있으므로 배열로 사용하기 위해서 + 값으로 끌어올리기 위해 +1000을 해주었다. 그리고 문제에서 설명해주는 0.5 칸에서 만나는 상황을 방지하기 위해 *2를 해주었다. 문제에서 주어진 좌표(x,y)와 배열을 행열이 반대이기 때문에 queue에 집어넣을 때 y x 로 집어넣어 주었고, 행 값의 시작이 0이므로 4000을 뺀 값을 행 값으로 넣어주었다.

다음 생각

모든 원자를 1칸씩 이동시키면서 살펴볼 것이므로 queue에서 빼내어 해당 방향으로 이동이 가능한지 체크한 후, 이동이 가능하다면 해당 칸의 값이 0인지 체크 해주었다. 0이 아니라면 이미 다른 원자가 있는 것이므로 충돌시켜 해당 배열의 값에 현 원자의 에너지 K를 더해주었다.

다다음 생각

여러번 충돌이 일어나도 처음 충돌위치에 도착한 원자는 이동하고자 하는 해당 배열의 값이 0이 였을 것이므로 빈 값이라 생각해 queue에 들어가고 해당 배열의 값을 자신이 가지고 있는 에너지 K 값으로 바꿔줄 것이다. 이후 도착한 원자들은 queue에 들어가지 않으므로 같은 시간대에 모든 원자들이 이동한 후 or 충돌한 후(K값이 더해진 후) queue에서 나왔을 때, 자기 위치의 배열 값이 자신의 K 값보다 크면 충돌이 일어났다는 뜻이므로 결과 변수인 result에 더해준 후 충돌한 원자는 없어져야하므로 continue를 통해 제거를 해주었다.

▶ 처음에는 충돌을 했나 안했나를 알기 위해서 HashSet<String>을 이용해서 해당 x,y좌표 + time 값을 이용해 비교를 해주었는데 메모리 초과의 원인이 되었다.

다다다음 생각

제출후 49개만 통과하여 보니 K가 0인 원자가 있어서 0일 경우를 처리해 주었다.

방안

1) K가 0일 경우 우선 101로 저장을 해둔 뒤, 개수를 카운트 하여 결과값에서 개수만큼 101을 빼주었다.

2) 테스트 케이스마다 map[4001][4001]을 새로 선언하여 주었는데 이것도 메모리 초과의 원인이 되었다.

▶ 원자가 충돌하면 사라지면서 0으로 만들고, 범위를 벗어나도 0으로 만들기 때문에 Field 영역에서 한 번 만 선언해 주는걸로 바꿔주었다.

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{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int tc = Integer.parseInt(br.readLine());
        for(int i=1;i<=tc;i++) {
            int n = Integer.parseInt(br.readLine());
            Pair[] arr = new Pair[n];
            for(int j=0;j<n;j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                arr[j] = new Pair(Integer.parseInt(st.nextToken()),
                        Integer.parseInt(st.nextToken()),
                        Integer.parseInt(st.nextToken()),
                        Integer.parseInt(st.nextToken()));
            }
            sb.append("#"+i+" "+solve(arr)+"\n");
        }        
        System.out.print(sb);
    }
    
    static int[][] map = new int[4001][4001];; 
    private static int solve(Pair[] arr) {
        Queue<Pair> queue = new LinkedList<>();
        // 0~4000 까지 사용하기 위해서 4001로
        for(int i=0;i<arr.length;i++) {
            // 주어진 좌표랑 배열상 x y기준이 다르기 때문에 교환
            // -를 없애기 위해 +1000
            int x = arr[i].y+1000;
            int y = arr[i].x+1000;
            int d = arr[i].d;
            int k = arr[i].k;
            if(k==0) k=101;
            // 0.5칸에서 만나는 것을 방지하기 위해서 *2 (0~4000)
            // 배열 상 x는 0 부터 시작하니 뒤집기
            queue.add(new Pair(4000-x*2, y*2, d, k));
            map[4000-x*2][y*2] = k;
        }
        int cntZero = 0;
        int result = 0;
        while(!queue.isEmpty()) {
            Pair t = queue.poll();
            // 이동하려고 하는데 자신의 K 보다 크면 충돌이 일어난 것.
            if(map[t.x][t.y]>t.k) {
                if(t.k==101) result-=101;
                result+=map[t.x][t.y];
                map[t.x][t.y] = 0;
                continue;
            }
            int tx = t.x;
            int ty = t.y;
            switch(t.d) {
            case 0: tx-=1; break;
            case 1:    tx+=1; break;
            case 2:    ty-=1; break;
            case 3:    ty+=1; break;
            }
            if(tx<0 || ty<0 || tx>4000 || ty>4000) {
                map[t.x][t.y] = 0;
                continue;
            }
            // 해당 좌표에 값이 있다면
            if(map[tx][ty]!=0) {
                if(t.k==101) cntZero++;
                map[tx][ty] += t.k;
                map[t.x][t.y] = 0;
            }else {
            // 값이 없다면
                map[tx][ty] = t.k;
                map[t.x][t.y] = 0;
                queue.add(new Pair(tx, ty, t.d, t.k));
            }
        }
        // zero 잘라주기
        result -= cntZero*101;
        return result;
    }
    
    static class Pair{
        private int x,y,k,d;
        public Pair(int x,int y,int d,int k) {
            this.x = x;
            this.y = y;
            this.d = d;
            this.k = k;
        }
    }
}