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

문제

SWEA 모의 SW 역량테스트 - 5648 원자 소멸 시뮬레이션

SW Expert Academy

 

---

문제 풀이

접근 방식

원자들이 소멸되면서 방출하는 에너지의 총합을 구하는 문제이다.

이 문제는 공개된 테스트 케이스가 2개밖에 없어서 정답률이 17.72% 밖에 안 되는 문제였다.

그래서 문제를 풀 때 예외를 찾기가 어려워 난항을 겪었던 문제였다.

그래도 댓글에 테스트 케이스를 제공해주신 분들이 있어서 많은 도움이 되었다.

 

이 문제는 크게 3가지 방법으로 문제를 풀어보고자 노력하였다.

첫 번째로 시도한 방법은  원자가 충돌하는 경우를 구해서 그때의 에너지들을 모두 더하는 방식으로 구현하였다.

원자가 충돌하는 경우는 이동하는 방향과 같은 직선 상에 있는 경우와 대각선 위치에 있어 직각으로 만나는 경우이다.

그래서 이동 방향에 따른 switch문으로 이를 구현해주었다.

이렇게 구현했을 때에는 50개의 테스트 케이스 중 22개만 맞춰 실패하였다.

이는 충돌하는 시간을 고려하지 않았기 때문이었다.

먼저 충돌해서 사라지는 원자들이 있을 텐데 이를 전혀 고려하지 않았다..

 

그래서 두 번째로 시도한 방법을 맵에서 원자들을 직접 이동시키는 방법이었다.

즉, 시간에 따라 원자들을 이동시키며 충돌하는 경우들을 찾아주었다.

이 방법으로 풀기 위해서는 0.5초에 만나는 경우도 있기 때문에 맵을 2배로 키워서 0.5초씩 이동시키는 게 중요하였다.

하지만 이 방법은 효율성이 떨어져서 시간 초과로 실패하였다..

 

세 번째로 시도한 방법은 첫 번째 방법에 충돌하는 시간과 위치도 함께 고려하여 구현하는 것이었다.

충돌 시간뿐만 아니라 위치도 알아야 같은 지점에서 만나는 모든 원소들의 에너지의 합을 구할 수 있기 때문이다.

이를 위해 collision 구조체를 만들어서 충돌하는 두 원자 사이의 거리와 두 원자들의 인덱스를 저장해주었다.

충돌하는 시간은 둘 사이의 거리와 비례하기 때문에 거리로 대신하였고,

위치는 거리와 첫 번째 원자의 인덱스의 조합으로 구해주었다.

원자는 같은 방향으로만 이동하기 때문에 같은 거리를 이동하는 한 원자와 만나는 다른 원자들은

거리와 한 원자의 인덱스만 알면 구할 수 있다.

이미 충돌한 원자들은 idx라는 set에 넣어놓고, 이 set 안에 들어 있는 원자가 포함된 collision은 무시해주었다.

 

---

풀이 코드 - C++

#include <iostream>
#include <cstring>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;
 
struct collision {
    int d;
    int a1;
    int a2;
};
 
bool cmp(collision a, collision b) {
    return a.d < b.d;
}
 
int main(int argc, char** argv) {
    int test_case, i, j, diff_x, diff_y, answer;
    int T, N;
    int atoms[1000][4];
    vector<collision> collisions;
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        cin >> N;
        memset(atoms, 0, sizeof(atoms));
        collisions.clear();
        for (i = 0; i < N; i++) {
            for (j = 0; j < 4; j++) {
                cin >> atoms[i][j];
            }
        }
 
        for (i = 0; i < N; i++) {
            if (atoms[i][3] == 0) continue;
            diff_x = atoms[i][0];
            diff_y = atoms[i][1];
            for (j = i + 1; j < N; j++) {
                diff_x -= atoms[j][0];
                diff_y -= atoms[j][1];
                switch (atoms[i][2]) {
                case 0:
                    if (diff_y <= 0 && ((diff_x == 0 && atoms[j][2] == 1)
                        || (diff_x == diff_y && atoms[j][2] == 2)
                        || (diff_x == -diff_y && atoms[j][2] == 3))) {
                        collisions.push_back({ abs(diff_y) + abs(diff_x), i, j });
                    }
                    break;
                case 1:
                    if (diff_y >= 0 && ((diff_x == 0 && atoms[j][2] == 0)
                        || (diff_x == diff_y && atoms[j][2] == 3)
                        || (diff_x == -diff_y && atoms[j][2] == 2))) {
                        collisions.push_back({ abs(diff_y) + abs(diff_x), i, j });
                    }
                    break;
                case 2:
                    if (diff_x >= 0 && ((diff_y == 0 && atoms[j][2] == 3)
                        || (diff_x == diff_y && atoms[j][2] == 0)
                        || (diff_x == -diff_y && atoms[j][2] == 1))) {
                        collisions.push_back({ abs(diff_y) + abs(diff_x), i, j });
                    }
                    break;
                case 3:
                    if (diff_x <= 0 && ((diff_y == 0 && atoms[j][2] == 2)
                        || (diff_x == diff_y && atoms[j][2] == 1)
                        || (diff_x == -diff_y && atoms[j][2] == 0))) {
                        collisions.push_back({ abs(diff_y) + abs(diff_x), i, j });
                    }
                    break;
                }
                diff_x += atoms[j][0];
                diff_y += atoms[j][1];
            }
        }
        if (collisions.empty())
            answer = 0;
        else {
            sort(collisions.begin(), collisions.end(), cmp);
            unordered_set<int> idx;
            int distance = collisions[0].d, first_idx = collisions[0].a1, len = collisions.size();
            answer = atoms[collisions[0].a1][3] + atoms[collisions[0].a2][3];
            idx.insert(collisions[0].a1);
            idx.insert(collisions[0].a2);
            for (i = 1; i < len; i++) {
                if (idx.size() == N) break;
                if (distance == collisions[i].d && first_idx == collisions[i].a1) {
                    if (idx.count(collisions[i].a2) != 0) continue;
                    answer += atoms[collisions[i].a2][3];
                    idx.insert(collisions[i].a2);
                }
                else {
                    if (idx.count(collisions[i].a1) != 0) continue;
                    if (idx.count(collisions[i].a2) != 0) continue;
                    distance = collisions[i].d, first_idx = collisions[i].a1;
                    idx.insert(collisions[i].a1);
                    idx.insert(collisions[i].a2);
                    answer += atoms[collisions[i].a1][3] + atoms[collisions[i].a2][3];
                }
            }
        }       
 
        cout << "#" << test_case << " " << answer << endl;
    }
    return 0;
}

실행 결과

실행 결과 : Pass (46ms)