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

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

 

[ 풀이 방법 ]

1. 파이어볼 초기화

  1. queue를 저장하는 2차원 배열과 구조체를 이용하여 이용해 각 좌표에 존재하는 파이어볼의 무게, 속력, 방향을 저장(board)

  2. queue에 파이어볼의 좌표를 R -> C가 작은 순서대로 저장(fireBalls)

#define X first
#define Y second

typedef pair<int, int> Cord;

struct FireBall {
    int m;
    int speed;
    int dir;
    
    FireBall(int m, int s, int d) : m(m), speed(s), dir(d) {}
};

 

2. 파이어볼 이동

  1. fireBalls 큐를 이용해 R -> C 좌표가 작은 순서대로 파이어볼을 모두 순회

  2. fireBalls에서 꺼낸 파이어볼 좌표를 이용해 board에서 해당 파이어볼의 무게, 속력, 방향을 조회

  - 좌표 순서대로 각 큐에 삽입하였기 때문에 fireBalls에서 꺼내진 파이어볼(좌표)과 board의 큐에서 꺼내진 파이어볼(무게, 속력, 방향)은 동일하다.

int dirX[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dirY[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int x = fireBalls.front().X;
int y = fireBalls.front().Y;
fireBalls.pop();
            
int m = board[x][y].front().m;
int speed = board[x][y].front().speed;
int dir = board[x][y].front().dir;
board[x][y].pop();

 

  3. 탐색된 속력과 방향을 이용해 파이어볼을 이동

int nx = x + dirX[dir]*speed%N;
int ny = y + dirY[dir]*speed%N;
nx %= N;
ny %= N;
if(nx < 0) nx += N;
if(ny < 0) ny += N;
            
board[nx][ny].emplace(m, speed, dir);

3. 이동이 끝난 후,  board를 탐색하여,

  1. 큐에 원소가 1개 들어있을 경우 fireBalls에 해당 좌표를 넣어준다.

  2. 큐에 원소가 여러개 들어있을 경우 무게, 속력을 모두 더하고 원소의 개수와 모든 원소가 홀수 또는 짝수인지 아닌지를 체크한다.

      무게로 (무게의 합/5)를 저장하고, 속력으로 (속력의 합/원소의 개수)를 저장하고, 모든 원소가 홀수 또는 짝수라면 방향으로 {0, 2, 4, 6}, 아니라면 {1, 3, 5, 7}을 저장하는 4개의 파이어볼을 생성하여 fireBalls에 저장한다.

  3. 무게가 0이라면 저장하지 않는다.

if(board[i][j].size() > 1) {
	int mSum = 0;
	int sSum = 0;
	int size = int(board[i][j].size());
	bool odd = true;
	bool even = true;

	while (!board[i][j].empty()) {
		mSum += board[i][j].front().m;
		sSum += board[i][j].front().speed;
		if(board[i][j].front().dir%2) even = false;
		else odd = false;
		board[i][j].pop();
	}
                    
	int m = mSum/5;
	if(m <= 0) continue;
	int speed = sSum/size;
	vector<int> dirs;
	if(odd || even) {
		dirs = {0, 2, 4, 6};
	} else {
		dirs = {1, 3, 5, 7};
	}
	for(int k = 0; k < 4; k++) {
		fireBalls.emplace(i, j);
	    board[i][j].emplace(m, speed, dirs[k]);
	}
	dirs.clear();
} else {
	fireBalls.emplace(i, j);
}

 

3. 위 과정을 K번 반복

 

[ 회고 ]

 파이어볼이 이동할 위치가 board의 범위를 벗어나는 경우를 처리하는 기능이 올바르게 동작하지 않아 OutOfBound 에러가 발생하였으나, 접근 방법과 구현 계획을 잘 세워두었기 때문에 에러가 발생한 원인을 빠르게 찾고 수정할 수 있었다.

 

[ 정답 코드 ]

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

#define X first
#define Y second

using namespace std;

struct FireBall {
    int m;
    int speed;
    int dir;
    
    FireBall(int m, int s, int d) : m(m), speed(s), dir(d) {}
};

int N, M, K;
vector<vector<queue<FireBall>>> board;
queue<Cord> fireBalls;

int dirX[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dirY[8] = {0, 1, 1, 1, 0, -1, -1, -1};

void solve() {
    
    while (K--) {
        
        while(!fireBalls.empty()) {
            int x = fireBalls.front().X;
            int y = fireBalls.front().Y;
            fireBalls.pop();
            
            int m = board[x][y].front().m;
            int speed = board[x][y].front().speed;
            int dir = board[x][y].front().dir;
            board[x][y].pop();
            
            int nx = x + dirX[dir]*speed%N;
            int ny = y + dirY[dir]*speed%N;
            nx %= N;
            ny %= N;
            if(nx < 0) nx += N;
            if(ny < 0) ny += N;
            
            board[nx][ny].emplace(m, speed, dir);
        }
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(board[i][j].empty()) continue;
                if(board[i][j].size() > 1) {
                    int mSum = 0;
                    int sSum = 0;
                    int size = int(board[i][j].size());
                    bool odd = true;
                    bool even = true;
                    
                    while (!board[i][j].empty()) {
                        mSum += board[i][j].front().m;
                        sSum += board[i][j].front().speed;
                        if(board[i][j].front().dir%2) even = false;
                        else odd = false;
                        board[i][j].pop();
                    }
                    
                    int m = mSum/5;
                    if(m <= 0) continue;
                    int speed = sSum/size;
                    vector<int> dirs;
                    if(odd || even) {
                        dirs = {0, 2, 4, 6};
                    } else {
                        dirs = {1, 3, 5, 7};
                    }
                    for(int k = 0; k < 4; k++) {
                        fireBalls.emplace(i, j);
                        board[i][j].emplace(m, speed, dirs[k]);
                    }
                    dirs.clear();
                } else {
                    fireBalls.emplace(i, j);
                }
            }
        }
    }
}

int calcSum() {
    int sum = 0;
    while(!fireBalls.empty()) {
        int x = fireBalls.front().X;
        int y = fireBalls.front().Y;
        
        sum += board[x][y].front().m;
        board[x][y].pop();
        fireBalls.pop();
    }
    return sum;
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    
    cin >> N >> M >> K;
    board.resize(N, vector<queue<FireBall>>(N));

    for(int i = 0; i < M; i++) {
        int x, y, m, s, d;
        cin >> x >> y >> m >> s >> d;
        x--; y--;
        board[x][y].emplace(m, s, d);
        fireBalls.emplace(x, y);
    }

    solve();
    
    cout << calcSum() << '\n';
    
    return 0;
}