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

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

원자력 발전소에서 근무하는 상원이는, 발전소에서 발생하는 에너지를 미리 계산하기 위해 원자들의 움직임을 시뮬레이션 하는 프로그램을 만들려고 한다.

 

원자들은 2차원 평면에서 이동하며 두 개 이상의 원자가 충돌 할 경우 충돌한 원자들은 각자 보유한 에너지를 모두 방출하고 소멸된다.

 

원자의 움직임은 다음과 같다.
 

1. 원자의 최초 위치는 2차원 평면상의 [x, y] 이다.

2. 원자는 각자 고유의 움직이는 방향을 가지고 있다. (상하좌우 4방향)

 - 상: y 가 증가하는 방향

 - 하: y 가 감소하는 방향

 - 좌: x 가 감소하는 방향

 - 우: x 가 증가하는 방향

3. 모든 원자들의 이동속도는 동일하다. 즉, 1초에 1만큼의 거리를 이동한다.

4. 모든 원자들은 최초 위치에서 동시에 이동을 시작한다.
5. 두 개 이상의 원자가 동시에 충돌 할 경우 충돌한 원자들은 모두 보유한 에너지를 방출하고 소멸된다.
 

           

                                    [그림-1]

 

[그림-1] 과 같이 원자들의 [x, y] 위치와 이동방향이 주어지고 각 원자들의 보유 에너지가 1 이라고 가정해보자. (실제 입력에서 원자들의 보유 에너지는 각각 다를 수 있다.)

충돌된 원자들이 소멸하면서 방출하는 에너지는 다음과 같다.

• 1초 후에 I, J 원자가 충돌 후 소멸하면서 2 에너지 방출
• 1.5초 후에 A, B 원자가 충돌 후 소멸하면서 2 에너지 방출
• 2초 후에 D, E, G, H 원자가 충돌 후 소멸하면서 4 에너지 방출
• 3초 후에 M, N 원자가 충돌 후 소멸하면서 2 에너지 방출

[그림-1]의 경우 시간이 흘러도 원자 C, F, K, L 은 영원히 충돌하지 않아 소멸되지 않는다.

따라서 원자들이 소멸되면서 방출하는 에너지의 총합은 10 이다.

 

N 개의 원자들의 [x, y] 위치, 이동 방향, 보유 에너지가 주어질 때 원자들이 소멸되면서 방출하는 에너지의 총합을 구하는 프로그램을 작성하라.

 

문제접근법.

 

1. 원자들을 하나씩 이동시키면서 충돌하는 것이 있는지 확인하기는 시간 복잡도가 너무 크다. 게다가, 원자들의 이동범위가 존재하지 않는다. 원자들의 충돌을 미리 파악해야 한다.

2. 원자 1번, 2번이 부딪히기 전에, 한 원자(1번)가 다른 원자(3번)랑 부딪힌다면, 1번과 2번 원자의 충돌은 무효가 된다. 원자가 충돌해서 에너지가 발생할 지 안 할지에 대해서 확실하게 구분해야 한다.

 

미리 원자들의 충돌을 파악하기 위해서, 행이 같거나, 열이 같은, 행과 열이 다르게 충돌하는 3가지 유형을 파악해야 한다. 또한 충돌하는 원자들의 인덱스, 시간을 우선순위큐에 삽입해서 원자가 이미 충돌해서 없어지지 않았는지 파악해야 해야 한다.

 

t초에 충돌한 원자들을 체크 배열에 기록해서, t+1초에 충돌할 수 없는 원자들이 되는 것은 당연한 사실이다.

하지만 중요한 것은, t초에서 여러 개의 원자들이 충돌할 수 있다.

예를 들어서, 큐에 (인덱스1, 인덱스2, 충돌시간)이 들어있다고 하자.

또한 각 원자들의 에너지는 1이라고 가정한다.

 

...

(0,1,1)

(3,4,1)

(0,2,1)

...

 

첫번째로, 0과 1에 대해서 충돌이 발생한다. 

두번째로, 3과 4에 대해서 충돌이 발생한다.

세번째로, 0과 2에 대해서 충돌이 발생할까?

 

2는 0과 부딪히기로 되어있었으므로, 충돌이 발생한다. 즉, 0은 1과 2와 동시에 충돌이 발생하는 것이다. 이 부분을 유의해서 코드를 작성해야 한다. 또한, 변수 타입에 대해서 double을 사용해야 하는 순간을 파악해야 한다. 

 

해설코드(C++).

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
 
typedef struct item {
    double x;
    double y;
    int d;
    int k;
    item(int _x, int _y, int _d, int _k) : x(_x), y(_y), d(_d), k(_k) {};
}item;
 
typedef struct boom {
    int idx1;
    int idx2;
    double time;
    boom(int _i1, int _i2, double _t) : idx1(_i1), idx2(_i2), time(_t) {};
}boom;
 
typedef struct myfunc {
    bool operator()(boom b1, boom b2) {
        return b1.time > b2.time;
    }
}myfunc;
 
int N;
int op[4][2] = { {0,1}, {0,-1},{-1,0},{1,0} };
int T;
int x, y, d, k;
int answer = 0;
 
int main(void) {
    freopen("input.txt", "r", stdin);
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cin >> N;
        vector<item> v;
        priority_queue<boom, vector<boom>, myfunc> p_q;
        answer = 0;
 
        for (int j = 1; j <= N; j++) {
            cin >> x >> y >> d >> k;
            v.push_back(item(x, y, d, k));
        }
 
        // Boom Check
        for (int i = 0; i < v.size(); i++)
        {
            for (int j = i + 1; j < v.size(); j++) {
                if (v.at(i).x == v.at(j).x) {
                    if (v.at(i).y > v.at(j).y) {
                        if (v.at(i).d == 1 && v.at(j).d == 0)
                            p_q.push(boom(i, j, (v.at(i).y - v.at(j).y) / 2));
                    }
                    else {
                        if (v.at(i).d == 0 && v.at(j).d == 1)
                            p_q.push(boom(i, j, (v.at(j).y - v.at(i).y) / 2));
                    }
                }
                else if (v.at(i).y == v.at(j).y) {
                    if (v.at(i).x > v.at(j).x) {
                        if (v.at(i).d == 2 && v.at(j).d == 3) {
                            p_q.push(boom(i, j, (v.at(i).x - v.at(j).x) / 2));
                        }
                    }
                    else {
                        if (v.at(i).d == 3 && v.at(j).d == 2) {
                            p_q.push(boom(i, j, (v.at(j).x - v.at(i).x) / 2));
                        }
                    }
                }
                else if (abs((int)v.at(i).x - (int)v.at(j).x) == abs((int)v.at(i).y - (int)v.at(j).y)) {
                    double time = abs((int)v.at(i).x - (int)v.at(j).x);
 
                    int n_i_x = v.at(i).x + op[v.at(i).d][0] * time;
                    int n_i_y = v.at(i).y + op[v.at(i).d][1] * time;
 
                    int n_j_x = v.at(j).x + op[v.at(j).d][0] * time;
                    int n_j_y = v.at(j).y + op[v.at(j).d][1] * time;
 
                    if (n_i_x == n_j_x && n_i_y == n_j_y)
                        p_q.push(boom(i, j, time));
                }
            }
        }
 
        double check[1000] = { 0 };
        memset(check, 0, sizeof(N));
            
        double temp_time = 0;
 
        // Boom
        while (!p_q.empty()) {
            if (temp_time == p_q.top().time) {
                if (check[p_q.top().idx1] == 0 && check[p_q.top().idx2] == temp_time) {
                    check[p_q.top().idx1] = temp_time;
                    answer += v.at(p_q.top().idx1).k;
                }
                else if (check[p_q.top().idx2] == 0 && check[p_q.top().idx1] == temp_time) {
                    check[p_q.top().idx2] = temp_time;
                    answer += v.at(p_q.top().idx2).k;
                }
                else if (check[p_q.top().idx1] == 0 && check[p_q.top().idx2] == 0) {
                    answer += (v.at(p_q.top().idx1).k + v.at(p_q.top().idx2).k);
                    check[p_q.top().idx1] = temp_time;
                    check[p_q.top().idx2] = temp_time;
                }
            }
            else {
                if (check[p_q.top().idx1] == 0 && check[p_q.top().idx2] == 0)
                {
                    answer += (v.at(p_q.top().idx1).k + v.at(p_q.top().idx2).k);
                    check[p_q.top().idx1] = p_q.top().time;
                    check[p_q.top().idx2] = p_q.top().time;
                    temp_time = p_q.top().time;
                }
            }
 
            p_q.pop();
        }
 
        cout << "#" << t << " " << answer << endl;
    }
    return 0;
}