[백준 20056] 마법사 상어와 파이어볼

조금 예전에 푼 문제긴 한데 헷갈리는 로직이 있어서 정리한다.

 

www.acmicpc.net/problem/20056

20056번: 마법사 상어와 파이어볼

 

구현 문제이고 규칙은 아래와 같다.

1. 모든 파이어볼이 방향으로 속력만큼 이동(이동중엔 경로가 겹쳐도 상관없다.)

2. 이동이 끝난 뒤 2개 이상의 파이어볼이 있는 칸에 한해서

2-1. 파이어볼이 하나로 합쳐짐

2-2. 다시 4개로 나눠짐

2-3. 4개의 파이어볼은

질량 = 질량 합 /5 -> 질량이 0인 경우 소멸

속력 = 속력합 / 파이어볼 수

방향 = if 모두 홀수 혹은 모두 짝수 -> 0 2 4 6 else 1 3 5 7

 

 

k번 1,2번을 반복한 후 남아있는 파이어볼 질량을 구하는 문제이다.

입력은

격자 크기, 파이어볼 개수, 명령 횟수

파이어볼 위치(row, col), 질량, 속도, 방향이다.

 

격자는 N*N 정사각형이다.

 

파이어볼을 기록하는 방법으로는 1) 이차원 배열 두개를 선언해서 이동 전과 이동 후를 기록하기

2) 벡터로 파이어볼의 정보를 기록하기가 있다.

 

여기선 1의 방법을 사용했다.

fireball 구조체를 선언해서 질량, 속도, 방향을 기록하고 이차원 배열에 위치를 기록한다.

 

움직임 기록하기

1. 방향으로 속도 만큼 이동하기

방향이 총 8개여서 0~7 인덱스에 따라 방향이 설정되도록 했다.

int dc[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dr[8] = {-1, -1, 0, 1, 1, 1, 0, -1};

원래 위치 + 속도 * 방향만큼 이동을 했을 때 격자에서 벗어나는 경우를 고려해줘야 한다.

이 부분때문에 포스팅을 한다.

 

처음 작성한 코드: idx가 n보다 크다면 혹은 1보다 작거나 같다면 (격자 길이를 1부터 n까지로 함)

int cal(int idx)
{
  if (idx > n)
  {
    idx %= n;
  }
  else if (idx < 1)
  {
    idx %= n;
    idx += n;
  }
  return idx;
}

참고로 음수 % 양수=음수이다.

이 부분이 문제인 이유는 idx가 n의 배수인 경우 idx가 0을 리턴한다....

따라서

int getLoc(int idx)
{
  idx = idx % n;

  if (idx < 1)
  {
    idx += n;
  }
  return idx;
}

 이렇게 짜야한다....이 부분으로 인해 삽질을 많이 했다

 

나머지 부분은 어렵지 않으니 패스한다.

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX 55

using namespace std;
int n, M, K, resM;
struct fireball
{
  int m, s, d;
};

vector<fireball> v[MAX][MAX];
vector<fireball> mv[MAX][MAX];

void emptyV(vector<fireball> nv[MAX][MAX])
{
  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= n; j++)
    {
      nv[i][j].clear();
    }
  }
}

int getLoc(int idx)
{
  idx = idx % n;

  if (idx < 1)
  {
    idx += n;
  }
  return idx;
}

//dir
int dc[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dr[8] = {-1, -1, 0, 1, 1, 1, 0, -1};

void move(int row, int col, const fireball &f)
{

  int nc = col + dc[f.d] * f.s;
  int nr = row + dr[f.d] * f.s;

  nc = getLoc(nc);
  nr = getLoc(nr);

  mv[nr][nc].push_back(f);
}

void divideBy4(int row, int col)
{
  int sumS = 0, sumM = 0, sze = mv[row][col].size();

  if (sze == 0) //파이어볼 없음
  {
    return;
  }

  if (sze == 1)
  {
    v[row][col].push_back(mv[row][col][0]);
    return;
  }

  bool odd = false, even = false;
  for (auto a : mv[row][col])
  {
    sumS += a.s;
    sumM += a.m;
    if (a.d % 2 == 0)
    {
      even = true;
    }
    else
    {
      odd = true;
    }
  }

  int divM = sumM / 5;
  int divS = sumS / sze;
  if (divM == 0) // 질량이 0인 파이어볼은 소멸
  {
    return;
  }

  if (even != odd) // 모두 홀수거나 짝수 방향
  {
    for (int i = 0; i < 8; i += 2)
    {

      v[row][col].push_back({divM, divS, i});
    }
  }
  else
  {
    for (int i = 1; i < 8; i += 2)
    {
      v[row][col].push_back({divM, divS, i});
    }
  }
}

int main(void)
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> M >> K;
  int r, c, m, s, d;
  for (int i = 0; i < M; i++)
  {
    cin >> r >> c >> m >> s >> d;
    v[r][c].push_back({m, s, d});
  }

  while (K--)
  {
    for (int i = 1; i <= n; i++)
    {
      for (int j = 1; j <= n; j++)
      {
        for (auto a : v[i][j])
        {
          move(i, j, a);
        }
      }
    }
    emptyV(v);
    for (int i = 1; i <= n; i++)
    {
      for (int j = 1; j <= n; j++)
      {
        divideBy4(i, j);
      }
    }
    emptyV(mv);
  }

  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= n; j++)
    {
      for (auto a : v[i][j])
      {
        resM += a.m;
      }
    }
  }

  cout << resM;
  return 0;
}