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

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

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

어쩌다 보니 1일 1상어는 기본이 되어버렸네요...

 

소요 시간

어이없게도 골드 2 기준 1시간 30분이 걸렸습니다;

 그 이유는 "격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다"라는 조건을 간과했기 때문입니다. 문제를 구상하면서 파이어볼이 n이나 1을 벗어나면 어떻게 되는 건지 알 수 없어서 의아했는데, 다시 한번 읽어보지 않고 그냥 그런 경우는 제외하는 것 같다고 멋대로 추측한 것이 패인이었네요. 제외가 되면 반드시 문제에서 명시합니다. 앞으로는 판단 불가한 경우가 있으면 무조건 문제를 다시 읽어 봐야겠어요...

 + 솔직히 이 문제가 왜 골드 4인지 모르겠습니다. 이 문제는 골드 3에 위치하고 있는 아기 상어(백준 사이트로 연결) 정도 난이도 아닐까요

 

구상

1. 파이어볼 이동 

2. 파이어볼 하나로 합치고 네개로 분리하기

 이 두가지만 시키는 대로 구현합니다. 질량이 0인 경우 소멸되는데, 애초에 질량이 줄어드는 경우는 2의 결과로만 발생하므로 2를 수행할 때 처리해 줍니다.

 정보 관리는 파이어볼을 구조체로 저장하여 NxN 배열에 배치했습니다. 여러 개 있을 수 있으니 구조체의 벡터를 배치합니다. 무려 3차원 구조체 배열이지만... 뭐 어때요... 다른 분들 포스팅을 봐도 다들 그렇게 하신 것 같습니다.

 애매한 지점이 '파이어볼 이동' 인데요, 파이어볼을 차례로 이동시키다가 겹치는 부분이 생기면 어떻게 해야 할지 난감할 수 있습니다.

저의 경우에는 파이어볼 구조체의 x,y를 수정한 뒤 따로 이 구조체의 벡터에 저장하고, 맵은 싹 비웠습니다. 그 뒤에 파이어볼 구조체 벡터를 하나씩 보면서 맵에 배치했습니다.

 주의할 점은 위치가 N을 넘어가면 모듈로 연산으로 0부터 돌아가야 한다는 것입니다!

 

코드

x,y좌표 범위를 0~n-1로 바꿔 풀었습니다.

#include <string>
#include <vector>
#include<iostream>
#include <climits>
#include<queue>
#include<cmath>
#include<algorithm>

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};

struct  fire {
    int r, c;
    int m, s, d;
    fire(int fr, int fc, int fm, int fs, int fd) {
        m = fm; s = fs; d = fd;
        r = fr; c = fc;
    }
    fire(int nx, int ny) {
        r = nx; c = ny;
    }
};

void move_fire(int n, vector<vector<vector<fire> > >& board) {
    vector<fire> fires;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            for(int k=0; k<board[i][j].size(); k++) {
                fire ball = board[i][j][k];
                int nx = (i + dx[ball.d]*ball.s); int ny = (j + dy[ball.d]*ball.s);
                while(nx < 0) nx += n;
                while(ny < 0) ny += n;
                nx %=n; ny %=n;
                fires.push_back(fire(nx, ny, ball.m, ball.s, ball.d));
            }
            board[i][j].clear();
        }
    }
    for(int i=0; i<fires.size(); i++) {
        fire ball = fires[i];
        board[ball.r][ball.c].push_back(ball);
    }
}

void sum_fire(int n, vector<vector<vector<fire> > >& board) {
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(board[i][j].size() < 2) continue;

            int m_sum = 0; int s_sum = 0; int ball_num = board[i][j].size();
            bool hasOdd = false; bool hasEven = false;
            for(int k=0; k<board[i][j].size(); k++) {
                m_sum += board[i][j][k].m;
                s_sum += board[i][j][k].s;
                if(board[i][j][k].d%2 == 0) hasEven = true;
                else hasOdd = true;
            }
            board[i][j].clear();

            if(m_sum/5 == 0) continue;
            for(int k=0; k<4; k++) {
                if(hasOdd && hasEven) {
                    board[i][j].push_back(fire(i, j, m_sum/5, s_sum/ball_num, 2*k+1));
                }
                else {
                    board[i][j].push_back(fire(i, j, m_sum/5, s_sum/ball_num, 2*k));
                }
            }
        }
    }
}



int solution(int n, int m, int k, vector<vector<vector<fire> > >& board) {

    for(int i=0; i<k; i++) {
        move_fire(n, board);
        sum_fire(n, board);
    }
    int sum_m = 0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            for(int k=0; k<board[i][j].size(); k++) {
                sum_m += board[i][j][k].m;
            }
        }
    }
    return sum_m;
}

int main(int argc, char** argv)
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<vector<fire> > > board;
    board.resize(n);
    for(int i=0; i<n; i++) {
        board[i].resize(n);
    }
    
    for(int i=0; i<m; i++) {
        int r, c, m, s, d;
        cin >> r >> c >> m >> s >> d;
        board[r-1][c-1].push_back(fire(r-1, c-1, m, s, d));
    }

    cout << solution(n, m, k, board) << endl;

    return 0;
}