[C++] 마법사 상어와 파이어볼 (20056번)

마법사 상어와 파이어볼

https://www.acmicpc.net/problem/20056

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

19279

7771

4732

36.591%

문제

어른 상어가 마법사가 되었고, 파이어볼을 배웠다.

마법사 상어가 크기가 N×N인 격자에 파이어볼 M개를 발사했다. 가장 처음에 파이어볼은 각자 위치에서 이동을 대기하고 있다. i번 파이어볼의 위치는 (ri, ci), 질량은 mi이고, 방향은 di, 속력은 si이다. 위치 (r, c)는 r행 c열을 의미한다.

격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.

파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정수로는 다음과 같다.

7	0	1
6		2
5	4	3

마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다.

1. 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.
   • 이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다.
2. 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.
   1. 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
   2. 파이어볼은 4개의 파이어볼로 나누어진다.
   3. 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.
      1. 질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
      2. 속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.
      3. 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.
   4. 질량이 0인 파이어볼은 소멸되어 없어진다.

마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 구해보자.

입력

첫째 줄에 N, M, K가 주어진다.

둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다.

서로 다른 두 파이어볼의 위치가 같은 경우는 입력으로 주어지지 않는다.

출력

마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 출력한다.

제한

• 4 ≤ N ≤ 50
• 0 ≤ M ≤ N2
• 1 ≤ K ≤ 1,000
• 1 ≤ ri, ci ≤ N
• 1 ≤ mi ≤ 1,000
• 1 ≤ si ≤ 1,000
• 0 ≤ di ≤ 7

---

문제풀이

문제 잘읽자. 맨 마지막 4번조건을 빼먹어서 조금 시간이 걸렸다.

각 배열 위치에 파이어볼이 여러개 올 수 있어서 처음엔 3차원 배열로 해야하나 고민했다. 근데 이러면 공간을 너무 잡아먹는것 같다는 생각이 들었다. 50x50x???이기 때문이다. 그래서 유동적으로 크기를 조절할 수 있는 벡터를 맨 마지막 부분에 사용하기로 바꿨다.

 

파이어볼의 m,s,d를 저장할 구조체를 생성하고 다음과 같이 선언하여 저장하였다. vector<fireBall> v[50][50];

그럼 각 배열에 vector를 넣을 수 있으므로 fireBall의 개수를 유동적으로 조절할 수 있다.

 

크게 두 부분으로 나누었다.

1. 파이어볼의 움직임을 구현한 함수

2. 이동이 끝난뒤 합치고, 분리하는 함수

 

파이어볼의 움직임을 구현한 함수

3번의 반복문을 돌려준다.

이 때 처음행과 마지막행, 처음 열과 마지막 열은 연결되어 있다.

speed 만큼 이동할 때 한 바퀴 이상 도는 경우를 방지하기 위해 이동하기 전에 % 연산을 이용하여 각 fireBall의 speed 값을 n 미만으로 설정해 주었다. 이 때 주의할 점이 처음 입력 받을 때 % 연산을 한 채로 저장하면 절대 안된다. 연산 값이 바뀌기 때문이다.

이렇게 해서 현재 인덱스와 fireBall의 스피드를 적절히 더하고, 뺴주어서 이동시켜주었다.

 

이동이 끝난뒤 합치고, 분리하는 함수

두개의 반복문을 통해 각 셀별로 파이어볼이 2개 이상인 곳을 찾는다.

찾은 경우 방향의 홀, 짝 체크를 위한 bool값, 질량의 합, 속도의 합을 저장할 변수를 선언한다.

셀의 fireBall을 순회하며 이 값들을 알맞게 할당 한뒤 질량이 0이 되지 않는다면 4개의 fireBall을 생성해준다.

 

#include <iostream>
#include <vector>

using namespace std;

int n, m, k;

struct FireBall {
    int mass;
    int speed;
    int direction;
};

vector<FireBall> v[50][50];

void moveFire() {
    vector<FireBall> v2[50][50];
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            for(int k=0; k<v[i][j].size(); k++) {
                int speed = v[i][j][k].speed % n;
                int r = i, c = j;
                if(v[i][j][k].direction == 0) {
                    if(i<speed) r = n-(speed-i);
                    else r = i-speed;
                }
                else if(v[i][j][k].direction == 1) {
                    if(i<speed) r = n-(speed-i);
                    else r = i-speed;
                    c = (j+speed)%n;
                }
                else if(v[i][j][k].direction == 2) {
                    c = (j+speed)%n;
                }
                else if(v[i][j][k].direction == 3) {
                    r = (i+speed)%n;
                    c = (j+speed)%n;
                }
                else if(v[i][j][k].direction == 4) {
                    r = (i+speed)%n;
                }
                else if(v[i][j][k].direction == 5) {
                    r = (i+speed)%n;
                    if(j<speed) c = n-(speed-j);
                    else c = j-speed;
                }
                else if(v[i][j][k].direction == 6) {
                    if(j<speed) c = n-(speed-j);
                    else c = j-speed;
                }
                else {
                    if(i<speed) r = n-(speed-i);
                    else r = i-speed;
                    if(j<speed) c = n-(speed-j);
                    else c = j-speed;
                }
                v2[r][c].push_back(v[i][j][k]);
            }
        }
    }
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            v[i][j] = v2[i][j];
        }
    }
}

void sumFire() {
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(v[i][j].size()>=2) {
                bool oddCheck = true;
                bool evenCheck = true;
                int mass_sum = 0;
                int speed_sum = 0;
                for(int k=0; k<v[i][j].size(); k++) {
                    if(v[i][j][k].direction%2 != 0) oddCheck = false;
                    if(v[i][j][k].direction%2 != 1) evenCheck = false;
                    mass_sum += v[i][j][k].mass;
                    speed_sum += v[i][j][k].speed;
                }
                int direction[4];
                if(oddCheck || evenCheck) {
                    direction[0] = 0;
                    direction[1] = 2;
                    direction[2] = 4;
                    direction[3] = 6;
                }
                else {
                    direction[0] = 1;
                    direction[1] = 3;
                    direction[2] = 5;
                    direction[3] = 7;
                }
                vector<FireBall> tmp;
                if(mass_sum/5 > 0) {
                    for(int a=0; a<4; a++) {
                        tmp.push_back({mass_sum/5, speed_sum/(int)v[i][j].size(), direction[a]});
                    }
                }
                v[i][j] = tmp;
            }
        }
    }
}

int main() {
    cin >> n >> m >> k;
    for(int i=0; i<m; i++) {
        int r, c, m, s, d;
        cin >> r >> c >> m >> s >> d;
        FireBall fb = {m, s, d};
        v[r-1][c-1].push_back(fb);
    }

    for(int i=0; i<k; i++) {
        moveFire();
        sumFire();
    }
    int answer = 0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            for(int l=0; l<v[i][j].size(); l++) {
                answer += v[i][j][l].mass;
            }
        }
    }
    cout << answer;
}