(c++)백준 20056번: 마법사 상어와 파이어볼

www.acmicpc.net/problem/20056

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

[풀이]

먼저 파이어볼의 질량, 속력, 방향을 저장하는 구조체 벡터 배열(vector<Ball>ball[51][51])에 파이어볼의 정보를 저장하는 것으로 시작하였다.

 

구현한 함수

1. 모든 파이어볼을 자신의 방향 d로 속력 s칸 이동시키는 함수(여러 파이어볼이 한 칸에 함께 있을 수 있다)

2. 2개 이상의 파이어볼이 있는 곳 조건에 맞게 처리하는 함수

※문제를 잘못 이해해서 2개 이상의 파이어볼을 합친다음 다시 나눌 때 같은 칸이 아니라 사방으로 퍼뜨리도록 해서 계속 틀렸다..같은 칸에 다시 저장하기!!

※s를 N으로 나눈 나머지만큼만 움직이게 하면 시간을 줄일 수 있다! (자기자리로 다시 돌아오는 경우 없애기)

 

#include <iostream>
#include <deque>
using namespace std;

struct Ball {
	int m;//질량
	int s;//방향
	int d;//속력
	int moved;//이번 명령에서 움직였는지
};

int N, M, K;
deque<Ball>ball[51][51];
const int dxy[][2] = { {-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1} };
int EvOd[] = { 0,2,4,6 };//합쳐지는 파이어볼의 방향이 모두 짝수이거나 홀수일 때
int Other[] = { 1,3,5,7 };//아닐 때
int moveLabel = 1;//움직인 경우

void moveBall() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int ballCnt = ball[i][j].size();
			if (ballCnt > 0) {
				for (int b = 0; b < ballCnt; b++) {
					//이미 움직였으면 break
					if (ball[i][j].front().moved == moveLabel)
						break;
					int nx = i;
					int ny = j;
					int m = ball[i][j].front().m;
					int s = ball[i][j].front().s;
					int d = ball[i][j].front().d;
					//제자리로 돌아오는 횟수 빼주기
					int ns = s % N;
					//다음 위치 구하기
					while (ns--) {
						nx += dxy[d][0];
						ny += dxy[d][1];
						if (nx == 0)
							nx = N;
						else if (nx == N + 1)
							nx = 1;
						if (ny == 0)
							ny = N;
						else if (ny == N + 1)
							ny = 1;	
					}
					ball[nx][ny].push_back({ m,s,d,moveLabel });
					ball[i][j].pop_front();
				}
			}
		}
	}
}

void moreThanTwo() {
	//2개 이상의 파이어볼 있는 곳 찾기
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int ballCnt = ball[i][j].size();
			if (ballCnt >= 2) {
				int nm = 0;//다음 질량
				int ns = 0;//다음 속력
				int nd;//다음 방향
				bool Even = true;
				bool Odd = true;
				for (int b = 0; b < ballCnt; b++) {
					nm += ball[i][j].front().m;
					ns += ball[i][j].front().s;
					if (ball[i][j].front().d % 2 == 0)
						Odd = false;
					if (ball[i][j].front().d % 2 == 1)
						Even = false;
					ball[i][j].pop_front();
				}
				nm /= 5;
				ns /= ballCnt;
				//질량이 0이면 소멸
				if (nm == 0) {
					ball[i][j].clear();
					continue;
				}
				//방향이 모두 홀수이거나 모두 짝수일 때
				if (Odd == true || Even == true) {
					for (int d = 0; d < 4; d++) {
						nd = EvOd[d];
						ball[i][j].push_back({ nm,ns,nd,moveLabel });
					}
				}
				else {
					for (int d = 0; d < 4; d++) {
						nd = Other[d];
						ball[i][j].push_back({ nm,ns,nd,moveLabel });
					}
				}
			}
		}
	}
}

//남은 파이어볼의 질량 합
int getMass() {
	int res = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int ballCnt = ball[i][j].size();
			if (ballCnt > 0) {
				for (int b = 0; b < ballCnt; b++)
					res += ball[i][j][b].m;
			}
		}
	}
	return res;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin >> N >> M >> K;
	int r, c, m, s, d;
	for (int i = 0; i < M; i++) {
		cin >> r >> c >> m >> s >> d;
		ball[r][c].push_back({ m,s,d,-moveLabel });
	}
	//이동 K번 명령
	while (K--) {
		//모든 파이어볼 이동
		moveBall();
		//2개 이상의 파이어볼이 남은 칸 처리
		moreThanTwo();
		moveLabel = -moveLabel;
	}
	cout << getMass() << '\n';
	return 0;
}