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

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

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

 

너무 고생했던 문제.....

고생 포인트

1. memset을 이용해 vector를 복사하려 했던 것..... 

      + arr[i][j] vector를 resize 시킨 후 copy해야한다.

vector<vector<int>> arr[51][51];

void copy_vec(vector< vector<int> > temp[][51]) {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			arr[i][j].resize(temp[i][j].size());
			copy(temp[i][j].begin(), temp[i][j].end(), arr[i][j].begin());
		}
	}
}

 

2. 런타임에러 발생... 

s가 너무 큰경우를 고려하지 않음. -> s % N으로 처리

 

3. 시간 초과 발생

-> vector<int> fireball를 생성하여 따로 정보 저장.

 

4. 질량이 0인 파이어볼은 소멸된다 조건 누락...

 

 

9시 20분에 시작해 12시 50분에 끝나버림....

#define _CRT_SECURE_NO_DEPRECATE

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int N, M, K;
vector<vector<int>> arr[51][51];
vector<vector<int>> fireball;
int answer;

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

void init() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			arr[i][j] = {};
		}
	}
}

void input() {
	cin >> N >> M >> K;

	int r, c, m, s, d;
	for (int i = 0; i < M; i++) {
		cin >> r >> c >> m >> s >> d;
		arr[r][c].push_back({ r,c,m,s,d });
		fireball.push_back({ r,c,m,s,d });
	}
}

void print() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 0; k < arr[i][j].size(); k++) {
				cout << i << " " << j << " " << arr[i][j][k][2] << " " << arr[i][j][k][3] << " "<< arr[i][j][k][4] << endl;
			}
		}
	}

	cout << "--------------" << endl;
}

void copy_vec(vector< vector<int> > temp[][51]) {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			arr[i][j].resize(temp[i][j].size());
			copy(temp[i][j].begin(), temp[i][j].end(), arr[i][j].begin());
		}
	}
}

void solve() {

	//1. 모든 파이어볼 이동.
	init();
	for (int i = 0; i < fireball.size(); i++) {
		int r = fireball[i][0];
		int c = fireball[i][1];
		int m = fireball[i][2]; //질량
		int s = fireball[i][3]; //속력
		int d = fireball[i][4]; //방향

		int nr = r + dr[d] * (s % N);
		if (nr > N) {
			nr -= N;
		}
		else if (nr <= 0) {
			nr += N;
		}

		int nc = c + dc[d] * (s % N);
		if (nc > N) {
			nc -= N;
		}
		else if (nc <= 0) {
			nc += N;
		}

		fireball[i][0] = nr;
		fireball[i][1] = nc;
		arr[nr][nc].push_back({ nr,nc,m,s,d });
	}

	//2. 
	vector<vector<int>> temp; //나누어진 4개의 파이어볼

	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			vector<vector<int>> fireballs = arr[r][c];

			if (fireballs.size() == 0) {
				continue;
			}
			else if (fireballs.size() == 1) {
				temp.push_back(fireballs[0]);
			}
			else { //2개 이상의 파이어볼인 경우
				int m_sum = 0;
				int s_sum = 0;
				vector<int> dir_sum;
				int total = fireballs.size(); //파이어볼의 개수
				
				for (int f = 0; f < total; f++) {
					m_sum += fireballs[f][2]; //질량의 합
					s_sum += fireballs[f][3]; //속력의 합
					dir_sum.push_back(fireballs[f][4]);
				}

				//방향 홀짝 확인
				int dir = dir_sum[0]%2;
				int new_dir = 0; //true면 방향이 모두 홀수이거나 모두 짝수
				for (int i = 1; i < total; i++) {
					if (dir != dir_sum[i] % 2) {
						new_dir = 1;
						break;
					}
				}

				//4개의 파이어볼로 나누어진다.
				int new_m = m_sum / 5;
				if (new_m > 0) {
					for (int i = 0, d = 0 + new_dir; i < 4; i++, d += 2) {
						temp.push_back({ r, c, new_m, s_sum / total, d });
					}
				}
			}
		}
	}
	
	init();
	fireball = {};
	for (int i = 0; i < temp.size(); i++) {
		arr[temp[i][0]][temp[i][1]].push_back(temp[i]);
		fireball.push_back(temp[i]);
	}

}

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

	//freopen("input.txt", "r", stdin);

	init();
	input();

	for (int i = 0; i < K; i++) {
		solve();
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (arr[i][j].size() > 0) {
				for (int k = 0; k < arr[i][j].size(); k++) {
					answer += arr[i][j][k][2];
				}
			}
		}
	}

	cout << answer << endl;

	return 0;
}