[C++] SWEA 5648 - 원자 소멸 시뮬레이션

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRFInKex8DFAUo&categoryId=AWXRFInKex8DFAUo&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=4 

SW Expert Academy

<풀이>

1. 원소들의 정보를 입력받는다.

2. 남은 원소들이 더이상 충돌하지 않을 때까지, 충돌한 원소들의 에너지의 합을 구해서 출력한다.

 

<해법>

1. 시뮬레이션 문제 X

=> 문제에서도 써있듯이, 처음에는 시뮬레이션 문제라고 생각했습니다. 저는 시간복잡도를 계산한 후에 시뮬레이션으로 풀면 안되겠다고 생각했습니다. 저는 시간복잡도를 1000초 x 원소 끼리의 충돌(1000 x 1000) = 1,000,000,000(10억)으로 계산했습니다. (문제를 다 푼 이후에 알게된 사실이지만, 이 문제를 시뮬레이션으로 풀 수 있고 많은 분들이 그렇게 풀었습니다.)

 

2. 수학적인 접근

=> 아래의 예시를 보겠습니다.

위 그림에서 볼 수 있듯이, 1000번의 시뮬레이션을 하지 않고 두 원소가 충돌한다는 사실을 수학적으로 알 수 있습니다. (원소1과 원소2의 방향, x좌표 차이, y좌표 차이 등을 통해 구합니다. 코드의 canCrash() 함수를 참조해주세요.)

따라서, 모든 원소들을 탐색하며 다른 원소들과의 충돌여부를 구해서 에너지를 더해주면 됩니다.

 

3. 두 원소가 정말 충돌할까?

=> 아래의 예시를 보겠습니다.

A1을 탐색하면 A3와 충돌한다고 나옵니다. 하지만 실제로 A3는 그 전에 A2와 충돌해서 사라지고, A1은 충돌하지 못합니다. 여기서 충돌 여부뿐만 아니라 충돌 좌표와 충돌 시간 정보도 필요하다는 것을 알 수 있습니다. 

 

4. 해법 순서 및 구현

(1) 해법 순서

① 모든 원소를 탐색한다.

② 두 원소가 충돌하면, 충돌 좌표와 충돌 시간을 구한다.

③ 같은 시간에 같은 좌표에서 충돌하는 원소들끼리 모은다.

④ 시간 오름차순으로 정리하고, 원소들을 충돌시킨다. 이전에 원소가 충돌했는지 확인하고, 두 개 이상의 원소가 충돌할 경우에만 충돌시키고 에너지를 방출한다.

 

(2) 구현

저는 위 그림과 같이 구현하였습니다.

 

#include <iostream>
#include <string.h>
#include <set>
#include <map>
#include <vector>
 
using namespace std;
 
//구조체 : 위치(x좌표, y좌표)
struct pos {
    int x, y;
};
 
//구조체 : 원자(원자 위치, 방향, 에너지)
struct atom {
    pos p;
    int dir;
    int energy;
};
 
//구조체 : 충돌(충돌 위치, 시간)
struct crash {
    pos p;
    int time;
};
 
//map의 key를 time이 작은 순서대로 정렬하기 위해
bool operator<(crash a, crash b) {
    if (a.time == b.time) {
        if (a.p.x == b.p.x) {
            return a.p.y < b.p.y;
        }
        return a.p.x < b.p.x;
    }
    return a.time < b.time;
}
 
int N;
vector<atom> atoms;
map<crash, set<int>> crashes;
bool crashed[1000];
int answer;
 
//원자 a1과 a2가 충돌할 수 있는지 판단하는 함수
bool canCrash(atom a1, atom a2) {
    int xGap = abs(a1.p.x - a2.p.x);
    int yGap = abs(a1.p.y - a2.p.y);
    switch (a1.dir) {
    case 0:
        if ((a2.dir == 1 && a1.p.x == a2.p.x && a1.p.y < a2.p.y) ||
            (a2.dir == 2 && a1.p.x < a2.p.x && a1.p.y < a2.p.y && xGap == yGap) ||
            (a2.dir == 3 && a1.p.x > a2.p.x && a1.p.y < a2.p.y && xGap == yGap)) return true;
        else return false;
    case 1:
        if ((a2.dir == 0 && a1.p.x == a2.p.x && a1.p.y > a2.p.y) ||
            (a2.dir == 2 && a1.p.x < a2.p.x && a1.p.y > a2.p.y && xGap == yGap) ||
            (a2.dir == 3 && a1.p.x > a2.p.x && a1.p.y > a2.p.y && xGap == yGap)) return true;
        else return false;
    case 2:
        if ((a2.dir == 0 && a1.p.x > a2.p.x && a1.p.y > a2.p.y && xGap == yGap) ||
            (a2.dir == 1 && a1.p.x > a2.p.x && a1.p.y < a2.p.y && xGap == yGap) ||
            (a2.dir == 3 && a1.p.x > a2.p.x && a1.p.y == a2.p.y)) return true;
        else return false;
    case 3:
        if ((a2.dir == 0 && a1.p.x < a2.p.x && a1.p.y > a2.p.y && xGap == yGap) ||
            (a2.dir == 1 && a1.p.x < a2.p.x && a1.p.y < a2.p.y && xGap == yGap) ||
            (a2.dir == 2 && a1.p.x < a2.p.x && a1.p.y == a2.p.y)) return true;
        else return false;
    }
}
 
//원자 a1과 a2가 충돌할 수 있다면, 충돌하는 위치와 시간을 구하는 함수
crash findCrash(atom a1, atom a2) {
    crash output;
    
    int xGap = abs(a1.p.x - a2.p.x);
    int yGap = abs(a1.p.y - a2.p.y);
    output.time = (xGap + yGap) / 2;
    switch (a1.dir) {
    case 0:
        if (a2.dir == 1) output.p = { a1.p.x, a1.p.y + (yGap / 2) };
        else output.p = { a1.p.x, a1.p.y + yGap };
        break;
    case 1:
        if (a2.dir == 0) output.p = { a1.p.x, a1.p.y - (yGap / 2) };
        else output.p = { a1.p.x, a1.p.y - yGap };
        break;
    case 2:
        if (a2.dir == 3) output.p = { a1.p.x - (xGap / 2), a1.p.y };
        else output.p = { a1.p.x - xGap, a1.p.y };
        break;
    case 3:
        if (a2.dir == 2) output.p = { a1.p.x + (xGap / 2), a1.p.y };
        else output.p = { a1.p.x + xGap, a1.p.y };
        break;
    }
 
    return output;
}
 
int main() {
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0;
        atoms.clear();
        crashes.clear();
        memset(crashed, false, sizeof(crashed));
        answer = 0;
 
        //입력
        cin >> N;
        for (int i = 0; i < N; i++) {
            int x, y, dir, energy;
            cin >> x >> y >> dir >> energy;
            atom a;
            a.p = { x * 2, y * 2 }; //좌표, 시간을 int로 관리하기 위해
            a.dir = dir;
            a.energy = energy;
            atoms.push_back(a);
        }
 
        /* 해법 */
        //1. 모든 원소들끼리의 충돌하는 지점과 시간을 구한다
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (canCrash(atoms[i], atoms[j])) {
                    crash c = findCrash(atoms[i], atoms[j]);
                    crashes[c].insert({i, j});
                }
            }
        }
 
        //2. 충돌하는 시간이 작은 것부터 원소를 충돌시킨다
        for (auto c : crashes) {
            int count = 0;
            for (auto index : c.second) {
                if (!crashed[index]) count++;
            }
            //원소가 두 개 이상일 경우에 충돌한다
            if (count > 1) {
                for (auto index : c.second) {
                    crashed[index] = true;
                    answer += atoms[index].energy;
                }
            }
        }
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

구현에 대해 알아볼 수 있는 문제였습니다.