BOJ 20056, 마법사상어와 파이어볼

Source: BOJ 20056 마법사상어와 파이어볼

마법사상어와 파이어볼

문제요약을 하자면 n X n 격자판 위에 m개의 파이어볼이 주어진다

각각의 파이어볼은 행, 열, 질량, 속력, 방향의 값을 갖고있으며

한번 이동시 자신의 방향으로 속력만큼 격자판 위를 이동한다 (단, 마지막 행/열은 첫 행/열과 연결되어있다)

이동이 모두 끝난 뒤 한칸위에 두개 이상의 파이어볼이 있으면 파이어볼은 4개로 나누어지고, 그 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.

1. 질량은 (합쳐진 파이어볼 질량의 합)/5이다.

2. 속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.

3. 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.

4. 질량이 0인 파이어볼은 소멸되어 없어진다.

k번 이동 후 남은 파이어볼의 질량 합을 구하는 문제

나는 fireball이라는 구조체를 선언하여 각 파이어볼들의 행, 열, 질량, 속력, 방향을 담았고

MAP[MAX][MAX]을 vector형으로 선언하여 이동 후 파이어볼의 위치를 관리해주었다

주의하여야 할 점으로 (단, 마지막 행/열은 첫 행/열과 연결되어있다)라는 점을 모듈러 연산으로 구할때

음수인 값을 고려하여 격자판의 크기 n을 한번 더한 후 모듈러 연산을 수행하였다

---

PS Logic

1. 파이어볼들을 관리해줄 구조체 선언 -> struct fireball{int r, c, m, s, d};

2. 맵의 크기 벡터형으로 선언(멤버함수 size()를 이용하기 위함) -> vector MAP[MAX][MAX];

3. 입력으로 받는 좌표값은 0-INDEX로 사용해야하므로 r–, c– 한 후 저장

4. k 번 반복으로 인한 while문 내에 solution 작성

5. 파이어볼의 이동 처리 -> ( 현재의 좌표값 + 속력*방향 + n) % n

6. 이동 후 파이어 볼의 상태를 MAP에 저장한 후 size함수를 통해 두개 이상이 들어있는 칸에 대해 처리

7. 새로운 4개의 파이어 볼을 임시 vector tmp에 저장

8. 기존 vector v에 vector tmp 복사

9. 반복한 후 파이어 볼의 질량 합 출력

---

#include <bits/stdc++.h>
using namespace std;

int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int n, m, k;
struct fireball{
  int r, c, m, s, d;
};
vector<fireball> v;
vector<fireball> MAP[51][51];
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>m>>k;
  for(int i=0; i<m; i++){
    int r, c, m, s, d;
    cin>>r>>c>>m>>s>>d;
    r--,c--;
    fireball f;
    f.r = r;
    f.c = c;
    f.m = m;
    f.s = s;
    f.d = d;
    v.push_back(f);
  }
  //solution
  while(k--){
    //MAP초기화
    for(int i=0; i<n; i++){
      for(int j=0; j<n; j++){
        MAP[i][j].clear();
      }
    }
    //파이어 볼의 방향으로 속력만큼 이동
    for(int i =0; i<v.size(); i++){
      v[i].r = (v[i].r + (((v[i].s)%n)*(dx[v[i].d]))+n ) % n;
      v[i].c = (v[i].c + (((v[i].s)%n)*(dy[v[i].d]))+n ) % n;
    }
    for(int i=0; i<v.size(); i++){
      MAP[v[i].r][v[i].c].push_back(v[i]);
    }
    vector<fireball> tmp;
    for(int i=0; i<n; i++){
      for(int j=0; j<n; j++){
        if(MAP[i][j].size()==0)continue;
        else if(MAP[i][j].size()==1) tmp.push_back(MAP[i][j][0]);
        else {
          int mess=0, speed=0, dir;
          bool flag = MAP[i][j][0].d % 2;
          bool checker = true;
          for(int k=0; k<MAP[i][j].size(); k++){
            mess += MAP[i][j][k].m;
            speed += MAP[i][j][k].s;
            if(flag != MAP[i][j][k].d % 2) checker = false;
          }

          mess /= 5;
          speed /= MAP[i][j].size();
          if(mess == 0) continue;
          int plus = checker ? 0 : 1;
          for(int n =0; n<4; n++){
            fireball newfireball;
            newfireball.r = i;
            newfireball.c = j;
            newfireball.m = mess;
            newfireball.s = speed;
            newfireball.d = n*2 + plus;
            tmp.push_back(newfireball);
          }
        }
      }
    }
    v = tmp;
  }
  int ans = 0;
  for(int i=0; i<v.size(); i++){
    ans += v[i].m;
  }
  cout<<ans;
}