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

문제

 

---

풀이

 

메모리면에서 그닥 효율적인 코드는 아닌 것 같지만 적어본다.

 

할 일은 2개밖에 없다

1. 파이어볼 이동

2. 파이어볼 분리

 

파이어볼의 상태를 저장할 구조체가 필요하겠고, 한 좌표에 둘 이상의 파이어볼이 있는지도 잘 체크해야 하고...

또 사라진 파이어볼을 어떻게 처리할지도 생각해야 한다.

 

아 그리고 격자의 크기가 최대 50인데 속력의 크기는 최대 1,000이다. 이걸 하나하나 움직이는건 당연히 비효율적이니 모듈러 연산을 사용해야 한다.

---

소스코드

 

#include <iostream>
#include <vector>

using namespace std;

struct info {
    bool is_remain;
    int r, c, m, s, d;
};

int N;
vector<vector<vector<int>>> board;
vector<info> fire;
pair<int, int> dir[8] = {{-1, 0}, {-1, 1}, {0,  1}, {1,  1}, {1,  0}, {1,  -1}, {0,  -1}, {-1, -1}};

void moveFire(int idx) { //파이어볼 이동
    info cur = fire[idx];

    //한번에 이동
    int row = (cur.r + (cur.s * dir[cur.d].first)) % N;
    int col = (cur.c + (cur.s * dir[cur.d].second)) % N;

    //음수 처리
    if (row < 0)
        row += N;
    if (col < 0)
        col += N;

    board[row][col].push_back(idx); //board에 표시
    fire[idx].r = row;
    fire[idx].c = col;
}

void splitFire(int row, int col) { //파이어볼 분리
    vector<int> fires = board[row][col];
    int mass = 0, speed = 0, odd_cnt = 0, even_cnt = 0, size = fires.size();
    for (int i = 0; i < size; i++) {
        info &cur = fire[fires[i]];
        cur.is_remain = false; //기존 파이어볼 삭제
        mass += cur.m; //총 질량
        speed += cur.s; //총 속력
        (cur.d % 2 == 0) ? even_cnt++ : odd_cnt++; //방향 홀짝 체크
    }
    if (mass / 5 == 0) //질량이 0인지 확인
        return;
    int init = 1; //합쳐지는 파이어볼의 방향
    if (odd_cnt == 0 || even_cnt == 0) //전부 홀수 or 짝수라면 0부터 시작
        init = 0;
    for (int i = 0; i < 4; i++) { //새로운 파이어볼 추가
        fire.push_back({true, row, col, mass / 5, speed / size, init});
        init += 2;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int M, K;

    cin >> N >> M >> K;
    for (int i = 0; i < M; i++) {
        int r, c, m, s, d;
        cin >> r >> c >> m >> s >> d;
        fire.push_back({true, r - 1, c - 1, m, s, d});
    }

    while (K--) {
        board.assign(N, vector<vector<int>>(N, vector<int>(0))); //board 초기화
        for (int i = 0; i < fire.size(); i++) {
            if (fire[i].is_remain) //활성화된 파이어볼이라면 이동
                moveFire(i);
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j].size() > 1) //파이어볼이 둘 이상 있다면
                    splitFire(i, j);
            }
        }
    }

    int result = 0;
    for (int i = 0; i < fire.size(); i++) {
        if (fire[i].is_remain) //남아있는 파이어볼만 질량 계산
            result += fire[i].m;
    }
    cout << result;
}

전체 소스코드다.

 

struct info {
    bool is_remain;
    int r, c, m, s, d;
};

int N;
vector<vector<vector<int>>> board;
vector<info> fire;
pair<int, int> dir[8] = {{-1, 0}, {-1, 1}, {0,  1}, {1,  1}, {1,  0}, {1,  -1}, {0,  -1}, {-1, -1}};

파이어볼의 상태를 저장할 구조체와 격자, 파이어볼 벡터, 그리고 방향 계산에 쓸 pair 배열도 만든다.

구조체에서 is_remain은 이 파이어볼이 여전히 격자에 존재하는지를 저장하는 bool 변수다.

 

    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int M, K;

    cin >> N >> M >> K;
    for (int i = 0; i < M; i++) {
        int r, c, m, s, d;
        cin >> r >> c >> m >> s >> d;
        fire.push_back({true, r - 1, c - 1, m, s, d});
    }

입력 받고

 

    while (K--) {
        board.assign(N, vector<vector<int>>(N, vector<int>(0))); //board 초기화
        for (int i = 0; i < fire.size(); i++) {
            if (fire[i].is_remain) //활성화된 파이어볼이라면 이동
                moveFire(i);
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j].size() > 1) //파이어볼이 둘 이상 있다면
                    splitFire(i, j);
            }
        }
    }

K번의 while문을 돈다.

 

        board.assign(N, vector<vector<int>>(N, vector<int>(0))); //board 초기화

먼저 격자의 상태는 매 루프마다 초기화 한다...기존 파이어볼을 삭제하고 이동하느니 초기화하는게 나을 것 같았다.

 

        for (int i = 0; i < fire.size(); i++) {
            if (fire[i].is_remain) //활성화된 파이어볼이라면 이동
                moveFire(i);
        }

모든 파이어볼에 대해 is_remain이 true라면 moveFire 함수를 호출해서 파이어볼을 이동한다.

 

void moveFire(int idx) { //파이어볼 이동
    info cur = fire[idx];

    //한번에 이동
    int row = (cur.r + (cur.s * dir[cur.d].first)) % N;
    int col = (cur.c + (cur.s * dir[cur.d].second)) % N;

    //음수 처리
    if (row < 0)
        row += N;
    if (col < 0)
        col += N;

    board[row][col].push_back(idx); //board에 표시
    fire[idx].r = row;
    fire[idx].c = col;
}

moveFire 함수는 간단하다.

 

    //한번에 이동
    int row = (cur.r + (cur.s * dir[cur.d].first)) % N;
    int col = (cur.c + (cur.s * dir[cur.d].second)) % N;

먼저 모듈러 연산으로 파이어볼의 새로운 좌표를 찾는다.

 

    //음수 처리
    if (row < 0)
        row += N;
    if (col < 0)
        col += N;

그 결과가 음수일 수도 있으니 그것도 고려한다.

 

    board[row][col].push_back(idx); //board에 표시
    fire[idx].r = row;
    fire[idx].c = col;

파이어볼의 새로운 위치를 격자에 표시하고 fire 자체도 r, c 값을 갱신한다.

 

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j].size() > 1) //파이어볼이 둘 이상 있다면
                    splitFire(i, j);
            }
        }

다시 메인으로 돌아와서 board를 돌다가 둘 이상의 파이어볼이 있다면 해당 좌표에 대해 splitFire 함수를 호출한다.

 

void splitFire(int row, int col) { //파이어볼 분리
    vector<int> fires = board[row][col];
    int mass = 0, speed = 0, odd_cnt = 0, even_cnt = 0, size = fires.size();
    for (int i = 0; i < size; i++) {
        info &cur = fire[fires[i]];
        cur.is_remain = false; //기존 파이어볼 삭제
        mass += cur.m; //총 질량
        speed += cur.s; //총 속력
        (cur.d % 2 == 0) ? even_cnt++ : odd_cnt++; //방향 홀짝 체크
    }
    if (mass / 5 == 0) //질량이 0인지 확인
        return;
    int init = 1; //합쳐지는 파이어볼의 방향
    if (odd_cnt == 0 || even_cnt == 0) //전부 홀수 or 짝수라면 0부터 시작
        init = 0;
    for (int i = 0; i < 4; i++) { //새로운 파이어볼 추가
        fire.push_back({true, row, col, mass / 5, speed / size, init});
        init += 2;
    }
}

이것도 엄청 어렵진 않다

 

    for (int i = 0; i < size; i++) {
        info &cur = fire[fires[i]];
        cur.is_remain = false; //기존 파이어볼 삭제
        mass += cur.m; //총 질량
        speed += cur.s; //총 속력
        (cur.d % 2 == 0) ? even_cnt++ : odd_cnt++; //방향 홀짝 체크
    }

먼저 해당 좌표의 모든 파이어볼에 대해 is_remain을 false로 바꿔준다. 합쳐져서 사라질 것이기 때문이다.

총 질량과 총 속력을 갱신하고 방향의 홀짝을 판단한다.

 

    if (mass / 5 == 0) //질량이 0인지 확인
        return;

그렇게 구한 총 질량을 5로 나눈 값이 0이라면 없는 파이어볼이니 그냥 리턴한다.

 

    int init = 1; //합쳐지는 파이어볼의 방향
    if (odd_cnt == 0 || even_cnt == 0) //전부 홀수 or 짝수라면 0부터 시작
        init = 0;

새로운 파이어볼의 방향을 0부터 시작할지 1부터 시작할지도 정하고...

 

    for (int i = 0; i < 4; i++) { //새로운 파이어볼 추가
        fire.push_back({true, row, col, mass / 5, speed / size, init});
        init += 2;
    }

그리곤 그냥 새로운 파이어볼을 파이어 벡터에 추가하면 된다.

 

    int result = 0;
    for (int i = 0; i < fire.size(); i++) {
        if (fire[i].is_remain) //남아있는 파이어볼만 질량 계산
            result += fire[i].m;
    }
    cout << result;

반복문을 다 돌면 남아있는 파이어볼들에 대해서만 질량을 전부 더해서 출력한다.