[SW Expert 5648] 원자 소멸 시뮬레이션

#문제

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

#풀이

굉장히 까다로웠던 문제이면서 시간이 엄청 오래 걸렸다.

시간 초과만 몇 번이 나왔는지 모르겠다.....

일단 원자들이 움직이는 것은 단순하다.

진짜 일직선만 쭈우욱...나아가기 때문에 너무 얕잡아 보았다.

여기서 중요한 점이 있다. 

만약 원자 하나는 [3,0]에서 왼쪽을 향해 가고있고 다른 원자는 [2,0]에서 오른쪽을 향해 가고있다면,  [2.5,0]인 곳에서 원자가 부딪히게 되어 정해진 1초가 아닌 0.5초에 원자들이 만나게 된다.

이 문제로 인해 여러 가지 방식으로 접근하게 되었다.

처음에는 단순히 맵(2000X2000 배열)을 만들어 초마다 원자들을 움직이면서 진행하려고 했다.

위와 같은 상황에서는 내가 갈 다음 위치에 원자가 있고 방향이 나를 향한다면 무조건 다음 시간에서는 충돌로 처리를 하였다.

하지만 맵을 만들어 돌리는것은 굉장히 어리석은 생각이었다.

맵을 한번 도는데만 4000000시간이 걸리며 이 원자들이 왼쪽 끝에서 오른쪽 끝으로 간다고 가정을 했을 때(가장 멀리가는 경우)에는 시간초 또한 2000번 엄청난 시간이 걸린다.

그리하여 원자들을 vector에 저장하고 원자들을 돌며, 확인하려 했다.

이 또한 많은 시간이 걸리게 된다. 하나하나 도는데만 N^2시간이 걸리며 아까 원자들이 가장 멀리 가는 경우로 생각했을 때는 엄청난 시간이 걸린다.

많은 고민을 해보았지만, 생각이 나지 않아 검색을 한 결과, 위에서 생각한 0.5초에 만나는 원자들을 찾을때 맵의 크기를 2배늘려 원자들을 배치 한다면 바로 해결이 된다. 또한 원자가 들어있는 벡터를 돌 때, 벡터만 사용하지 않고 맵까지 같이 사용한다면 시간을 줄일 수 있다.

그 이유는 원자들 간의 충돌에 있다. 

우선 모든 원자들을 돌며 다음 위치로 넘어가며 그 위치에 자신의 에너지를 저장해 놓는다. 

만약 이때, 맵 밖으로 나간다면 이 원자는 영원히 부딪칠 수 없기 때문에 에너지를 0으로 바꿔 놓는다. 

또 이전에 맵에 저장해 놓았던 자신의 에너지도 0으로 만들어 놓는다.

모든 원자들을 이동 시켰다면 다시 에너지가 0이 아닌 원자들만, 현재 위치의 맵에 저장되어있는 에너지 값과 원자 고유의 에너지 값을 비교하여 다르다면 무조건 충돌이 일어난 셈이다. 

따라서 이를 총 에너지에 더해주고나서 해당 맵을 0으로 처리하며 원자 또한 0으로 처리한다.(폭발 처리)

나머지 충돌되는 원자들은 이미 맵을 0으로 해놓았으므로 더해도 상관 없으며, 자동적으로 자신의 에너지도 0으로 만들어버린다.

이 과정이 모두 끝난 뒤에 원자들이 저장된 벡터에서 에너지가 0인 즉, 폭발되거나 맵 밖으로 나간 원자들을 제거해준다.

이를 계속하다 원자들의 에너지가 0이 된다면 종료 시키고 총 에너지를 출력한다.

움직임과 충돌 확인을 할 때 각각 벡터를 한번만 돌기 때문에 N시간이 두번 걸리게 된다.

또한 0으로 만들어준 원자들을 빼기 때문에 시간이 더 적게 걸릴것 같다는 생각이 든다.

엄청난 시도 끝에.. 성공하게 되어 너무 기뻤지만... 한편으로는 너무 단순하게 생각하는 경향이 있는 것을 깨닫게 해주는 문제였다.

#코드

#include <iostream>
#include <vector>
using namespace std;
 
struct Atom{
    int x;
    int y;
    int dir;
    int energy;
};
 
int N;
 
vector<Atom> atoms;
int map[4001][4001];
 
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
 
int calcTotalEnergy(){
    int totalEnergy = 0;
    while(!atoms.empty()){
        int size = (int)atoms.size();
        for(int i = 0; i < size; i++){
            map[atoms[i].y][atoms[i].x] = 0;
            int dir = atoms[i].dir;
            int nx = atoms[i].x + dx[dir];
            int ny = atoms[i].y + dy[dir];
            if(nx < 0 || nx > 4000 || ny < 0 || ny > 4000) {
                atoms[i].energy = 0;
                continue;
            }
            atoms[i].x = nx;
            atoms[i].y = ny;
            map[ny][nx] += atoms[i].energy;
        }
        //충돌인 지역 확인.
        for(int i = 0; i < size; i++){
            if(atoms[i].energy == 0) continue;
            int x = atoms[i].x;
            int y = atoms[i].y;
            if(map[y][x] != atoms[i].energy){
                totalEnergy += map[y][x];
                map[y][x] = 0;
                atoms[i].energy = 0;
            }
        }
        vector<Atom> tempVector;
        tempVector.assign(atoms.begin(), atoms.end());
        atoms.clear();
        int tempVectorSize = (int)tempVector.size();
        for(int i = 0; i < tempVectorSize; i++){
            if(tempVector[i].energy != 0){
                atoms.push_back(tempVector[i]);
            }
        }
    }
    return totalEnergy;
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie();cout.tie();
    int tc;
    cin >> tc;
    for(int t = 1; t <= tc; t++){
        cin >> N;
        for(int i = 0; i < N; i++){
            Atom atom;
            cin >> atom.x >> atom.y >> atom.dir >> atom.energy;
            atom.x += 1000;
            atom.y += 1000;
            atom.x *= 2;
            atom.y *= 2;
            atoms.push_back(atom);
        }
        cout << "#" << t << " " << calcTotalEnergy() << "\n";
    }
    return 0;
}