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

[문제]

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

SW Expert Academy

[풀이]

 

1) 큐를 사용하면 시간 초과가 발생한다. 

 

2) 원자가 하나도 없을 때와 하나만 존재할 때는 ans = 0 이다. 왜냐하면 어떤 다른 원자와도 부딪힐 수 없기 때문이다. 

 

3)

• 원자는 서로 같은 좌표를 향해 움직일 때 에너지를 방출할 수 있다. 
• 좌표의 범위는 (-1000 <=  <= 1000) 이고 0.5도 허용하기 때문에 (서로 같은 좌표로 움직일 때 0.5씩 움직인다.)
• 좌표를 1000 + *2로 만들어준다. 
• 즉, 좌표가 -1000일 때는 0이 되는 것이다. 그러면 음수를 처리할 필요 없고 0.5 라는 단위도 처리할 필요 없다. 

4) 무한 반복에서 원자들이 이동하면서 서로 같은 좌표로 가게 되면 map[][]을 한 좌표에 위치한 원자의 수만큼 증가시킨다.

-> 2이상이면 그 안의 원자들은 에너지를 방출하고 소멸한다. 

---

 

#include <iostream>
#include <vector>
#include <cstring>
 
#define MAX 4001
 
using namespace std;
 
int n, map[MAX][MAX], ans = 0;
 
typedef struct Atom
{
    int x, y, dir, energy;
    bool live;
    Atom() {}
    Atom(int _x, int _y, int _d, int _e, bool _l) : x(_x), y(_y), dir(_d), energy(_e), live(_l) {}
};
 
vector<Atom> atoms;
 
int dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0};
 
bool allDie()
{
    for (int i = 0; i < atoms.size(); i++)
    {
        if (atoms[i].live)
            return false;
    }
    return true;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int t;
    cin >> t;
 
    for (int tc = 1; tc <= t; ++tc)
    {
        memset(map, 0, sizeof(map));
        ans = 0;
        atoms.clear();
 
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            int x, y, d, k;
 
            cin >> x >> y >> d >> k;
 
            x = (x + 1000) * 2;
            y = (y + 1000) * 2;
 
            atoms.push_back(Atom(x, y, d, k, true));
            map[x][y] = 1;
        }
        //input
 
        //가지치기
        if (atoms.size() == 0 || atoms.size() == 1)
        {
            cout << "#" << tc << " " << ans << '\n';
            continue;
        }
 
        //원자를 움직이고 중복 검사
        while (1)
        {
            int tmp_energe = 0;
            if (allDie())
                break;
 
            for (int i = 0; i < atoms.size(); i++)
            {
                if (!atoms[i].live)
                    continue;
 
                int x = atoms[i].x;
                int y = atoms[i].y;
 
                map[x][y] = 0;
                //이동할 거니까 0으로 초기화
 
                int dir = atoms[i].dir;
 
                int nx = x + dx[dir];
                int ny = y + dy[dir];
 
                if (nx < 0 || nx >= MAX || ny < 0 || ny >= MAX)
                {
                    atoms[i].live = false;
                    continue;
                }
                map[nx][ny] += 1; //맵 안에 세포의 개수를 늘린다. 
                atoms[i].y = ny;
                atoms[i].x = nx;
            }
 
            for (int i = 0; i < atoms.size(); i++)
            {
                if (!atoms[i].live)
                    continue;
                //같은 좌표에 있는 세포들을 제거한다. 
 
                if (map[atoms[i].x][atoms[i].y] >= 2)
                {
                    for (int j = 0; j < atoms.size(); j++)
                    {
                        if (i == j)
                            continue;
                        if (!atoms[j].live)
                            continue;
 
                        if (atoms[i].x == atoms[j].x && atoms[i].y == atoms[j].y)
                        {
                            //같은 좌표에 위치
                            tmp_energe += atoms[j].energy;
                            atoms[j].live = false;
                        }
                    }
                    tmp_energe += atoms[i].energy;
                    atoms[i].live = false;
                    map[atoms[i].x][atoms[i].y] = 0;
                }
            }
            ans += tmp_energe;
        }
 
        cout << "#" << tc << " " << ans << '\n';
    }
 
    return 0;
}