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

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

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

#include <cstdio>
#include <vector>
#include <cstring>
int N, M, K;
struct _ft
{
	int idx;	// 벡터의 몇번째 칸에 위치해 있는가
	int r, c;
	int m, d, s;
};

_ft Fire[10000 + 2];
_ft Tmp[10000 + 2];

std::vector<int> Board[50 + 2][50 + 2];

int Same[4] = { 0, 2, 4, 6 };
int Diff[4] = { 1, 3, 5, 7 };


void debug()
{
	for (int i = 1; i <= M; i++) {
		printf("[%d] %d %d %d %d %d\n", Fire[i].idx, Fire[i].r, Fire[i].c, Fire[i].m, Fire[i].s, Fire[i].d);
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (!Board[i][j].empty()) printf("%d ", Board[i][j].size());
			else printf("%d ", 0);
		}
		printf("\n");
	}
}



void input()
{
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 1; i <= M; i++) {
		// 서로 다른 두 파이어볼의 위치가 같은 경우는 입력으로 주어지지 않는다
		// 처음 입력 시 무조건 0번째 벡터에 위치
		scanf("%d %d %d %d %d", &Fire[i].r, &Fire[i].c, &Fire[i].m, &Fire[i].s, &Fire[i].d);
	}
}



void move()
{
	static int dir_x[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
	static int dir_y[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };

	for (int i = 1; i <= M; i++) {		// M개의 파이어볼을 이동한다. 
		_ft data = Fire[i];
	
		int nr = data.r + (data.s * dir_x[data.d] % N);
		if (nr < 1) nr += N;
		else if (nr > N) nr -= N;
		int nc = data.c + (data.s * dir_y[data.d] % N);
		if (nc < 1) nc += N;
		else if (nc > N) nc -= N;
		Board[nr][nc].push_back(i);
		Fire[i].idx = Board[nr][nc].size() - 1;
		Fire[i].r = nr;
		Fire[i].c = nc;
	}
}



int chk()
{
	int num = 1;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (!Board[i][j].empty() && Board[i][j].size() == 1) {	// 임시 구조체에 Fire 모든 내용 옮겨줌
				Tmp[num] = Fire[Board[i][j][0]];
				num++;
				Board[i][j].clear();
			}
			if (!Board[i][j].empty() && Board[i][j].size() >= 2) {
				int tm = 0;	// 총질량
				int ts = 0;	// 총속력
				int even = 0;
				int odd = 0;
				// 연산 진행
				int sz = Board[i][j].size();
				for (int k = 0; k < sz; k++) {
					tm += Fire[Board[i][j][k]].m;
					ts += Fire[Board[i][j][k]].s;
					if (Fire[Board[i][j][k]].d % 2 == 0) odd++;
					else even++;
				}
				Board[i][j].clear();			// 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다. 
				if (tm / 5 == 0) continue;
				for (int k = 0; k <4; k++) {	// 파이어볼은 4개의 파이어볼로 나누어진다. 
					Tmp[num].idx = k;
					Tmp[num].r = i;
					Tmp[num].c = j;
					Tmp[num].m = tm / 5;
					Tmp[num].s = ts / sz;
					if (even == sz || odd == sz) Tmp[num].d = Same[k];
					else Tmp[num].d = Diff[k];
					num++;
				}
			}
		}
	}
	return num - 1;
}



void init_info(int cnt)
{
	for (int i = 1; i <= M; i++) {
		Fire[i] = { 0, 0, 0, 0, 0, 0 };
	}
	for (int i = 1; i <= cnt; i++) {
		Fire[i] = Tmp[i];
	}
	M = cnt;
	for (int i = 1; i <= M; i++) {
		Tmp[i] = { 0, 0, 0, 0, 0, 0 };
	}
}



void simul()
{
	for (int cmd = 0; cmd < K; cmd++) {	// K번 명령한다. 
		move();
		int cnt = chk();		// 파이어볼이 합쳐지고 나눠지면서 그 수가 바뀐다.
		init_info(cnt);			// Tmp 구조체에 있는 파이어볼 정보들 Fire 구조체로 옮겨줄것임
	}
}



int output()
{
	int total = 0;
	for (int i = 1; i <= M; i++) {
		total += Fire[i].m;
	}
	return total;
}



int main()
{
	input();
	simul();
	int ans = output();
	printf("%d\n", ans);
	return 0;
}

주석... 참고.....

 

---

++ 22.10.27 다시 풀어봄 

딱히 더 좋은 코드 같지는 않지만, 그리고 처음 풀 때 난 OOB가 같은 이유인지는 잘 기억 안나지만 일단 기록해본다.. 

#include <cstdio>
#include <vector>
#include <list>
int N, M, K;

struct _st
{
	int r, c;
	int m, s, d;

}FB[10000 + 2];
_st TB[10000 + 2];	// temp

std::vector<int> V[50 + 2][50 + 2];	// 구조체의 몇번째 파이어볼이 담겼는지
std::vector<int> C[50 + 2][50 + 2];	// temp

int same_dir[4] = { 0, 2, 4, 6 };
int diff_dir[4] = { 1, 3, 5, 7 };

void input()
{
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 1; i <= M; i++) {
		int r = 0, c = 0, m = 0, s = 0, d = 0;
		scanf("%d %d %d %d %d", &r, &c, &m, &s, &d);
		FB[i] = { r, c, m, s, d };
		V[r][c].push_back(i);
	}
}


void move_ball()
{
	// 상 대 우 대 하 대 좌 대
	static int dir_x[8] = { -1, -1, 0, 1, 1, 1, 0,  -1 };
	static int dir_y[8] = { 0,  1,  1, 1, 0, -1, -1, -1 };

	for (int i = 1; i <= M; i++) {
		int x = FB[i].r;
		int y = FB[i].c;
		int m = FB[i].m;
		int d = FB[i].d;
		int s = FB[i].s;

		int nx = x + dir_x[d] * (s % N);
		if (nx < 1) nx += N;
		else if (nx > N) nx -= N;
		int ny = y + dir_y[d] * (s % N);
		if (ny < 1) ny += N;
		else if (ny > N) ny -= N;

		FB[i] = { nx, ny, m, s, d };	// 갱신
		C[nx][ny].push_back(i);
	}

	// V init
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			V[i][j].clear();
		}
	}
}


void gt_two()
{
	int tnum = 1;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (C[i][j].size() >= 2) {
				int mass = 0;
				int velo = 0;
				int cnt = C[i][j].size();
				int even = 0;
				int odd = 0;
				
				for (int k = 0; k < cnt; k++) {
					mass += FB[C[i][j][k]].m;
					velo += FB[C[i][j][k]].s;
					if (FB[C[i][j][k]].d % 2) odd++;
					else even++;
				}

				if (mass / 5 > 0) {
					for (int b = 0; b < 4; b++) {
						if (even == cnt || odd == cnt) TB[tnum] = { i, j, mass / 5, velo / cnt, same_dir[b] };
						else TB[tnum] = { i, j, mass / 5, velo / cnt, diff_dir[b] };
						V[i][j].push_back(tnum);
						tnum++;
					}
				}
			}
			else if (C[i][j].size() > 0) {
				TB[tnum] = FB[C[i][j][0]];
				V[i][j].push_back(tnum);
				tnum++;
			}
			C[i][j].clear();
		}
	}

	//FB init
	for (int i = 1; i <= M; i++) {
		FB[i] = { 0, 0, 0, 0, 0 };
	}

	M = tnum - 1;
}



void mig_info()
{
	for (int i = 1; i <= M; i++) {
		FB[i] = TB[i];
	}

	// TB init
	for (int i = 1; i <= M; i++) {
		TB[i] = { 0, 0, 0, 0, 0 };
	}
}



void simulation()
{
	for (int cmd = 0; cmd < K; cmd++) {
		move_ball();
		//debug();
		gt_two();
		mig_info();
		//debug_fb();
	}
}

int output()
{
	int total = 0;
	for (int i = 1; i <= M; i++) {
		total += FB[i].m;
	}
	return total;
}


int main()
{
	input();
	simulation();
	int ans = output();
	printf("%d\n", ans);
	return 0;
}

여기서 중요한 점은 50 * 50 맵에서 각 칸에 파이어볼이 모두 2개 이상 존재하고, 합쳐져서 4개가 새로 만들어졌을 때 이다. 

따라서 파이어볼을 저장하는 구조체 사이즈를 2500(처음에 50 * 50맵이라서 이렇게 할당함) 이 아니라 50 * 50 * 4 즉 최소 10000을 할당해주어야 한다.