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

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

---

1. 이해하기

• 원자들은 2차원 평면에서 이동하며 두 개 이상의 원자가 충돌할 경우 충돌한 원자들은 각자 보유한 에너지를 모두 방출하고 소멸된다.
• 원자는 각자 고유의 움직이는 방향을 가지고 있다.
• 모든 원자들의 이동속도는 동일하다. 즉, 1초에 1만큼의 거리를 이동한다.
• 원자들이 소멸되면서 방출하는 에너지의 총합을 구하는 문제.
• 시뮬레이션 문제.

---

2. 구현하기

• 원자들은 0.5초 후에도 만나면 충돌하여 에너지를 방출한다. 따라서 이동 구간을 2배로 늘려주면 된다.

• 원자들의 이동을 구현한다.

  • 이때, 입력이 y,x로 주어지기 때문에 이동방향을 맞춰서 잘 구현해주어야 한다.

  bool out_of_bound(int x, int y) {
      return x < 0 or x > 4001 or y < 0 or y > 4001;
  }
  
  void move() {
      for(int i = 0; i < N; i++) {
          Atom& now = atom[i];
          if(now.ene == 0 or out_of_bound(now.x,now.y)) continue;
          now.x+=dx[now.dir]; now.y+=dy[now.dir];
      }
  }

• 원자들이 현재 위치를 맵에 표시하고 충돌이 일어났다면 충돌한 원자들의 에너지들을 모두 구해준다.

  • 이때, 맵을 0으로 초기화하기 위해서 memset을 쓰면 시간이 오버된다. 따라서 memset을 쓰지 않는 방법을 생각해야 한다.

  int get_energy() {
      for(int i = 0; i < N; i++) {
          Atom now = atom[i];
          if(now.ene == 0 or out_of_bound(now.x,now.y)) continue;
          map[now.x][now.y] += now.ene;
      }
  
      int ret = 0;
      for(int i = 0; i < N; i++) {
          Atom& now = atom[i];
          if(now.ene == 0 or out_of_bound(now.x,now.y)) continue;
          if(map[now.x][now.y] == now.ene) {
              map[now.x][now.y] = 0;
          }
          else {
              now.ene = 0;
              ret += map[now.x][now.y];
              map[now.x][now.y] = 0;
          }
      }
      return ret;
  }

• 원자가 0에서 4000까지 움직이는 데는 4001초가 걸리므로 이 정도 시간이 지날 때까지 반복하면서 원자의 충돌 에너지를 구한다.

  int simulate() {
      int ret = 0;
      for(int i = 0; i <= 4002; i++) {
          move();
          ret += get_energy();
      }
      return ret;
  }

---

3. 전체 코드

#include <iostream>
using namespace std;
struct Atom{
    int x,y,dir,ene;
}atom[1000];
int map[4002][4002];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,-1,1};
int N;

bool out_of_bound(int x, int y) {
    return x < 0 or x > 4001 or y < 0 or y > 4001;
}

void move() {
    for(int i = 0; i < N; i++) {
        Atom& now = atom[i];
        if(now.ene == 0 or out_of_bound(now.x,now.y)) continue;
        now.x+=dx[now.dir]; now.y+=dy[now.dir];
    }
}

int get_energy() {
    for(int i = 0; i < N; i++) {
        Atom now = atom[i];
        if(now.ene == 0 or out_of_bound(now.x,now.y)) continue;
        map[now.x][now.y] += now.ene;
    }

    int ret = 0;
    for(int i = 0; i < N; i++) {
        Atom& now = atom[i];
        if(now.ene == 0 or out_of_bound(now.x,now.y)) continue;
        if(map[now.x][now.y] == now.ene) {
            map[now.x][now.y] = 0;
        }
        else {
            now.ene = 0;
            ret += map[now.x][now.y];
            map[now.x][now.y] = 0;
        }
    }
    return ret;
}

int simulate() {
    int ret = 0;
    for(int i = 0; i <= 4002; i++) {
        move();
        ret += get_energy();
    }
    return ret;
}

void input() {
    cin >> N;
    for(int i = 0; i < N; i++) cin >> atom[i].y >> atom[i].x >> atom[i].dir >> atom[i].ene;
    for(int i = 0; i < N; i++) {
        atom[i].x = (atom[i].x+1000)*2;
        atom[i].y = (atom[i].y+1000)*2;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    for(int t = 1; t <= T; t++) {
        input();
        cout << '#' << t << ' ' << simulate() << '\n';
    }
    return 0;
}