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

SWExpertAcademy의 원자 소멸 시뮬레이션(5648) 문제이다.

[ 문제풀이 ]

1) 문제가 굉장히 어렵다. 구현해야 할 내용도 많고 난이도도 있는 문제같다..

   천천히 단계적으로 진행해 나가보자.

   먼저 본인은 원자들의 정보를 저장하는 구조체를 만들었고 이 구조체를 자료형으로 갖는 Vector에 원자들에 대한 정보를

   담았다.

   구조체 내에서 관리하는 변수로는 { x좌표, y좌표, 진행방향, Energy, 살았는지 죽었는지 판단을위한 bool형 변수 }

   이렇게 총 5개의 데이터를 관리해 주었다.

   그럼 이제 입력부터 차근차근 해보도록 하자.

2) 일단 맵이 우리가 기존에 받던 맵과는 조금 다른 형태이다. 왜냐하면 음수 좌표를 받을 수 있기 때문이다.

   우리가 맵을 만든다고해도, 음수 좌표는 배열의 인덱스로 가져갈 수 없기 때문에 뭔가 다른 방법이 필요하다.

   따라서 본인은 입력받는 (x, y)좌표에 각각 + 1000을 해주었다.

   + 1000을 해준 이유는 문제의 조건에서 "원자의 처음 위치는 -1000이상 1000이하 입니다" 라고 했기 때문이다.

   즉, (-1000, -1000)을 입력받는다고 해도 실제로 우리가 맵에 저장할 때에는 (0, 0)을 저장하게 되는 것이다.

   또 하나는 맵의 전체 범위이다. 사실 이 부분은 구현하는 사람에 따라서 필요가 없는 경우일 수도 있는데 본인은 원자들이

   충돌하는 것을 실제로 맵에서 옮기면서 진행하였다.

   그렇다면 무슨 문제점이 발생할까?? 아래 그림을 한번 봐보도록 하자.

  

   문제에 있는 그림에서 A와 B 부분만 캡쳐해온 사진이다. 실제로 문제에 있는 그림에서는 좌표가 정해져있지만

   쉽게 이해하기 위해서 좌표를 임의로 설정해보겠다.

   A를 (0, 0), B를 (0, 3) 으로 생각하자. 그리고 A와 B가 충돌하는 시간은 1.5 초 후에 충돌한다고 되어있다.

  

   즉 본인이 파랑색으로 막대기를 그어놓은 시점에서 둘이 만나서 터진다는 것을 의미한다.

   본인은 원자들이 충돌하는 것을 알아내기 위해서 실제로 맵에서 원자들을 옮겼다고 했는데 우리가 옮길 때 저부분이

   구현이 가능할까??

   맵에서 실제로 옮기게 되면 1초 후에 A는 (0, 1)로 B는 (0, 2)로 갈 것이고, 2초 후에는 A는 (0, 2), B는 (0, 1)로 갈것이다.

   배열에서 (0, 1.5), (0, 1.5)는 표현을 할 수가 없다.

   이 부분을 해결을 위해서 본인은 맵의 전체크기에 x2를 해주었고, 입력받는 좌표도 x2를 해 주었다.

   왜 x2일까??

   (0, 0) 과 (0, 1)에 서로 충돌하는 방향으로 움직이는 두 원자가 있다고 생각해보자. 문제상에 의하면 이 원자들은 0.5초 후에

   충돌하게 된다. 하지만 0.5초가 표현이 불가능하다. 즉, 0.5초를 1로 표현한 것이다. 0.5초를 1로 표현하기 위해서는 x2를

   해줘야 한다. 그렇다면 일단 이해가 안되더라도 말하는대로 x2를 해보자.

   (0, 0)은 (0, 0)이 될 것이고 (0, 1)은 (0, 2)가 될 것이다. 이 둘은 1초후에 (0, 1)에서 만나서 터지게 된다.

   즉, 맵의 전체범위가 4000 x 4000이 된다.

   처음에 -1000 ~ 1000 이였는데, 음수값 좌표를 해결하기 위해서 +1000을 해주게 되면, 0 ~ 2000이고, 0,5초의 문제를

   해결하기 위해서 x2를 해주면 0 ~ 4000이 된다. 즉, 맵의 전체 크기는 4000 x 4000 짜리 맵이 된다.

  

   물론, 위의 과정 필요없이 입력을 받아서 정답을 도출해 낼 수도 있겠지만 본인은 저렇게 구현했다.

2) 이제 실제로 원자를 움직여야 한다.

   언제까지 움직여야할까?? 쉽게 생각해서 모든 원자가 다 죽을때까지 움직여 주면 된다.

   사실 맵에서 원자들을 표현하고 움직여 주었다고 했는데 정확하게 맵에 "해당 좌표에 있는 원자의 갯수"를 저장해 주었다.

   초기상태에는 원자들이 중복된 위치에 주어지지 않는다고 했으므로 아마 원자들이 있는 위치는 다 1로 표현이 되 있을 것이다.

   이 '1'이 원자를 '1'로 표현한 것이 아닌, 해당좌표에 현재 원자가 '1'개 있음을 뜻한다.

   이제부터는 어떻게 움직였는지 맵의 값을 어떻게 관리했는지 알아보자.

  

3) 맵을 움직이는 과정은 다음과 같다.

   지금부터 사용되는 (x, y)는 원자가 있었던 좌표를 의미하고, (nx, ny)는 원자가 이동한 좌표를 의미한다.

   1. 원자를 해당 원자의 진행방향에 맞게 움직여준다.

   2. 원자가 이동할 좌표인 (nx, ny)가 맵의 범위 내인지 확인한다.

      - 맵의 범위 내라면 MAP[x][y] = 0, MAP[nx][ny]++ 가 될 것이다.

      - 맵의 범위 밖이라면 MAP[x][y] = 0 이되고, 해당 원자는 죽었다는 것을 표시하기 위해서 false로 표시될 것이다.

      - 또한, 맵의 범위 내에 있을 때 원자들의 정보를 저장한 Vector에서 해당 원자의 x, y 좌표도 nx, ny로 바꿔준다.

   3. 원자들을 모두 돌면서, MAP[nx][ny] >= 2 이상인 곳에 대해서 폭팔한 원자들을 모두 죽였다고 표시해준다.

      - 이과정에서는 맵을 4000 x 4000을 반복한 것이 아닌, 원자들의 정보가 저장되어 있는 vector의 size만큼만 반복을 해줬다.

      - 구체적으로 MAP의 값이 2이상인 곳이 나온다면, 원자들의 갯수만큼 for문을 돌면서 현재 MAP의 좌표와 같은 좌표에

        존재하는 원자들을 죽여줌과 동시에 Energy를 계산했다.

        이 부분은 그림으로 이해해보자. 말로 설명하기 힘들다.....

        이 경우에 DEGH 원자들은 2초후에 만나서 폭팔하게 된다.

        즉, 파랑색으로 동그라미 친 부분을 (a, b)라고 한다면, MAP[a][b] = 4일 것이다.

        그렇다면 원자들을 모두 돌면서 현재 좌표가 (a, b)인 원자들을 찾아서 모두 죽여줬다는 말이다 !

     위의 과정을 계속해서 반복해주면 된다. 언제까지 ? 모든 원자가 다 죽을 때 까지 !

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
 
#define endl "\n"
#define MAX 4001
using namespace std;
 
typedef struct
{
    int x;
    int y;
    int dir;
    int Energy;
    bool Live;
}Atom_Info;
 
int N, Total_Energy;
int MAP[MAX][MAX];
vector<Atom_Info> Atom;
 
int dx[] = { 0, 0, -1, 1 };
int dy[] = { 1, -1, 0, 0 };
 
void Initialize()
{
    N = 0;
    Total_Energy = 0;
    Atom.clear();
    memset(MAP, 0, sizeof(MAP));
}
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int x, y, dir, k;
        cin >> x >> y >> dir >> k;
        x = (x + 1000) * 2;
        y = (y + 1000) * 2;
        Atom_Info Temp;
        Temp.x = x;
        Temp.y = y;
        Temp.dir = dir;
        Temp.Energy = k;
        Temp.Live = true;
        Atom.push_back(Temp);
        MAP[x][y] = 1;
    }
}
 
bool All_Die()
{
    for (int i = 0; i < Atom.size(); i++)
    {
        if (Atom[i].Live == true)
        {
            return false;
        }
    }
    return true;
}
 
void Move_Atom()
{
    while (1)
    {
        int Temp_Energy = 0;
        if (All_Die() == true) break;
 
        for (int i = 0; i < Atom.size(); i++)
        {
            if (Atom[i].Live == false) continue;
 
            int x = Atom[i].x;
            int y = Atom[i].y;
            int dir = Atom[i].dir;
 
            int nx = x + dx[dir];
            int ny = y + dy[dir];
 
            if (nx >= 0 && ny >= 0 && nx < MAX && ny < MAX)
            {
                MAP[x][y] = 0;
                MAP[nx][ny] = MAP[nx][ny] + 1;
                x = nx;
                y = ny;
                Atom[i].x = x;
                Atom[i].y = y;
            }
            else
            {
                Atom[i].Live = false;
                MAP[x][y] = 0;
            }
        }
 
        for (int i = 0; i < Atom.size(); i++)
        {
            if (Atom[i].Live == false) continue;
            int x = Atom[i].x;
            int y = Atom[i].y;
 
            if (MAP[x][y] >= 2)    // 한개라면 터지지는 않으니 최소 2개 이상이 만났을 때
            {
                for (int j = 0; j < Atom.size(); j++)
                {
                    if (i == j) continue;
                    if (Atom[j].Live == false) continue;
 
                    int xx = Atom[j].x;
                    int yy = Atom[j].y;
 
                    if (x == xx && y == yy)
                    {
                        Temp_Energy = Temp_Energy + Atom[j].Energy;
                        Atom[j].Live = false;
                    }
                }
 
                Temp_Energy = Temp_Energy + Atom[i].Energy;
                Atom[i].Live = false;
                MAP[x][y] = 0;
            }
 
        }
        Total_Energy = Total_Energy + Temp_Energy;
    }
}
 
void Solution()
{
    if (Atom.size() == 0 || Atom.size() == 1)
    {
        Total_Energy = 0;
        return;
    }
    Move_Atom();
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Total_Energy << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}