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

1초에 한번씩 원자들이 움직이는데 충돌할 경우 그대로 에너지를 방출하고 소멸한다

이 때 방출된 에너지의 총합을 구하는 문제이다.

 

문제의 이름부터 아주 고정관념이 한참 생겨 무조건 시뮬레이션으로 풀어야지! 라는 생각에 여러번 틀렸던 문제이다.

 

하지만 생각해보면 충돌할 경우만 생각하여 에너지만 구해주고 끝내면 되는 문제이다.

( 시간이 무한히 흐른다면 ( 이 문제의 경우 최대 2000초(문제 내에서 시간) ) 충돌되지 않은 원자들은 밖으로 빠져 나간다. 빠져나간 원자들은 고려하지 않아도 된다. 이 원자들은 평생 만날 일이 없기 때문이다.) 

 

주변에 어떤 친구는 0초부터 2000초 까지 for문을 통해서 모든 경우를 다해준 경우도 있었고

 

이전 포스트들에서 본 것처럼 또 충돌 나는 것들은 여러개의 Map을 통해서 해결하려고도 해보았다.

 

하지만... 함정인 것을 깨닫고 ( 물론 시뮬레이션으로 푼 사람들도 있으나 매우 비효율 적이었다. )

 

이 문제의 경우 중요 포인트라고 볼 수 있는 것은

1초에 한칸씩 움직이지만 마주 보고 있는 원자들이 사이에 아무 칸도 없다면 0.5초에 충돌후 소멸할 수도 있다는 점이다.

 

이 것에 대해서 고려하지 않고 풀면 무조건 틀리게 되어있다.

 

그리고 정말 귀찮게 x,y 좌표로 되어 그걸 편하게 계산하려면 어떻게 해야하는 지에 대해서 공책을 펴고 무수히 고민을 해보았다.... 썩을 ㅠ

 

이 문제의 경우 해결법은 다음과 같다.

소스코드를 보면 이중 for문을 돌면서 확인을 해주는데 이 때 a[2] == 0  인 if문 ( 위로 올라갈 경우 ) 을 대상으로 상세히 설명하면 다음과 같다.

어디서 긁어 온 것 같지만 같이 스터디하는 사람들에게 설명하느라 말투가 갑자기 달라졌다 하하 스터디 보다 여기가 말쓰기가 더 편하다 사실 아무도 소통을 안하기 때문이다 하하하하하하

 

a[2] == 0 일때를 먼저 예를 들어주면

위로 가는 경우 이 원자가 다른 원자와 만날 수 있는 방법은 3가지 입니다

자신보다 위에 있는 원자중 왼쪽 오른쪽에서 오는 경우

그리고 위에서 아래로 내려오는 경우

1. 위에서 아래로 내려오는 경우는 두점의 좌표를 비교하여 거리 나누기 2를 해주시면 됩니다( 이때 일부러 double로 선언하여 0.5초 일때도 가능하게 만들었습니다. )
2. 왼쪽 오른쪽의 경우 쉽게i, j로 생각하면 (0,0)이 오른쪽으로 (2,2)가 위로 간다면 (0,0)에서 (0,2)로 가는 길이와 (2,2)에서 (0,2)로 가는 길이가 같다면 두점은 만나게 됩니다.
3. 위 두가지 경우를 생각하여 pq에 넣어주는데 ( 만나는데 걸리는 시간, 만나는 1번 점의 index, 만나는 2번점의 index ) 순으로 넣어줍니다. (버블 정렬 처럼 모든 경우를 다해보기 때문에 4번 항목처럼 모든 경우가 다 들어갑니다.)
4. pq에는 한 점에서 2개이상의 점이 만나는 경우까지 포함하여 다 들어가게 되는데 그렇기 때문에 3개점이 만날때는 어떻게 해요라는 것은 불필요한 질문이 됩니다.
5. pq의 정렬 기준의 경우 의아할 수 있는데 아래 check배열을 채우는 것에 있어 점들 사이의 거리가 작은 것 부터 처리를 해주어야 하기 때문에 먼저 점들의 간격순으로 정렬하였고 ( 이때, return (int)(o1[0]-o2[0]); 를 하면 되지 않느냐 할 수 있지만 0.5의 경우 0이 리턴 되어 다르게 정렬 될 수 있음을 생각하시면 됩니다.
6. 나머지는 i,j의 오름차순으로 정렬하였습니다.
7. 이제 pq를 돌면서 check 배열을 채워주게 되는데 큐에서 빼낸 값의 1번과 2번이 ( temp[1]과 temp[2] ) 의 check값이 0이라면 둘다 각각 채워주게 되고 ( 이때 만나는 시간을 넣어주었다. )
8. 둘 중 하나만 0이라면 3개 이상의 원자가 만나는 것이므로 다시 만나는 시간을 넣어주었다.
9. 모든 경우의 수를 다 해보았기 때문에 check배열이 채워질 것이고 check 배열에 0이상의 값이 있다 ( 최소 0.5 라도 ) 그러면 사라지는 원자이기 때문에 이때 리스트의 i 번째 값을 total에 더해주어 값을 출력하였다.

 

전체 소스코드를 보세요 ! 215ms 밖에 나오지 않는 매우 짧은 속도입니다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
  
public class Solution {
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        int N = 0;
        PriorityQueue<double[]> pq = null;
        ArrayList<int[]> list = null;
        int[] arr = null;
        int x = 0;
        int y = 0;
        int d = 0;
        int e = 0;
        String[] tmp = null;
        int[] a = null;
        int[] b = null;
        double[] check = null;
        double[] temp = null;
        int totalE = 0;
        for(int t = 1; t <= T; ++t){
            list = new ArrayList<int[]>();
            pq = new PriorityQueue<double[]>(new Comparator<double[]>() {
                @Override
                public int compare(double[] o1, double[] o2) {
                    if(o1[0] < o2[0])	return -1;
                    else if(o1[0] > o2[0])	return 1;
                    else if(o1[1] != o2[1])	return (int)(o1[1]-o2[1]);
                    else if(o1[2] != o2[2])	return (int)(o1[2]-o2[2]);
                    return 0;
                }
            });
            N = Integer.parseInt(br.readLine());
            for(int i = 1; i <= N; ++i){
                tmp = br.readLine().split(" ");
                y = 2000 - Integer.parseInt(tmp[1]);
                x = 2000 + Integer.parseInt(tmp[0]);
                d = Integer.parseInt(tmp[2]);
                e = Integer.parseInt(tmp[3]);
                list.add(new int[] {y, x, d, e});
            }
            for(int i = 0; i < N - 1; ++i){
                a = list.get(i);
                if(a[2] == 0) {
                	for(int j = i + 1; j < N; ++j){
                		b = list.get(j);
                		//a[2] = 상
                		if(a[0] > b[0]){
                			if(b[2] == 1 && a[1] == b[1]){
                				//하                                                 
                				pq.add(new double[]{(a[0] - b[0]) / 2.0, i, j});
                			}else if(b[2] == 2 && a[0] - b[0] == b[1] - a[1]){
                				//좌                     
                				pq.add(new double[]{a[0] - b[0], i, j});
                			}else if(b[2] == 3 && a[0] - b[0] == a[1] - b[1]){
                				//우
                				pq.add(new double[]{a[0] - b[0], i, j});
                			}
                		}
                	}
                }else if(a[2] == 1) {
                	for(int j = i + 1; j < N; ++j){
                        b = list.get(j);
                        //a[2] = 하
                        if(a[0] < b[0]){
                            if(b[2] == 0 && b[1] == a[1]){
                                //상                                             
                                pq.add(new double[]{(b[0] - a[0]) / 2.0, i, j});
                            }else if(b[2] == 2 && b[0] - a[0] == b[1] - a[1]){
                                //좌                     
                                pq.add(new double[]{b[0] - a[0], i, j});
                            }else if(b[2] == 3 && b[0] - a[0] == a[1] - b[1]){
                                //우
                                pq.add(new double[]{b[0] - a[0], i, j});
                            }
                        }
                    }
                }else if(a[2] == 2) {
                	for(int j = i + 1; j < N; ++j){
                        b = list.get(j);
                        //a[2] = 좌
                        if(a[1] > b[1]){
                            if(b[2] == 3 && a[0] == b[0]){
                                //우                                                     
                                pq.add(new double[]{(a[1] - b[1]) / 2.0, i, j});
                            }else if(b[2] == 0 && b[0] - a[0] == a[1] - b[1]){
                                //상                     
                                pq.add(new double[]{a[1] - b[1], i, j});
                            }else if(b[2] == 1 && a[0] - b[0] == a[1] - b[1]){
                                //하
                                pq.add(new double[]{a[1] - b[1], i, j});
                            }
                        }
                    }
                }else if(a[2] == 3) {
                	for(int j = i + 1; j < N; ++j){
                        b = list.get(j);
                        //a[2] = 우
                        if(a[1] < b[1]){
                            if(b[2] == 2 && a[0] == b[0]){
                                //좌                                                     
                                pq.add(new double[]{(b[1] - a[1]) / 2.0, i, j});
                            }else if(b[2] == 0 && b[0] - a[0] == b[1] - a[1]){
                                //상                     
                                pq.add(new double[]{b[1] - a[1], i, j});
                            }else if(b[2] == 1 && a[0] - b[0] == b[1] - a[1]){
                                //하
                                pq.add(new double[]{b[1] - a[1], i, j});
                            }
                        }
                    }
                }
            }           
            check = new double[N];
            while(!pq.isEmpty()){
                temp = pq.poll();
                if(check[(int)temp[1]] == 0 && check[(int)temp[2]] == 0){
                    check[(int)temp[1]] = temp[0];
                    check[(int)temp[2]] = temp[0];
                }else if(check[(int)temp[1]] == temp[0]){
                    check[(int)temp[2]] = temp[0];
                }
            }
            totalE = 0;
            for(int i = 0; i < N; ++i){
                if(check[i] > 0){
                	totalE += list.get(i)[3];
                }
            }
            bw.write("#"+t+" "+totalE+"\n");
        }
        bw.close();
        br.close();
    }
}