[백준 21610] 마법사 상어와 비바라기

++ 22.11.07 새로 짠 코드도 썩 마음에 들진 않지만 이전 꺼 보다는 나아서 갱신해본다. 

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

21610번: 마법사 상어와 비바라기

#include <cstdio>
#include <cstring>
#include <vector>
int N, M;
int A[50 + 2][50 + 2];
int CMD[100 + 2][2];

struct _st
{
	int x, y;
};

std::vector<_st> V;
int cloud[50 + 2][50 + 2];
int tmp_move[50 + 2][50 + 2];
int tmp_magic[50 + 2][50 + 2];
std::vector<_st> T;



void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &A[i][j]);
		}
	}
	for (int m = 0; m < M; m++) {
		// d, s
		scanf("%d %d", &CMD[m][0], &CMD[m][1]);
	}

	// 초기 비바라기 시전
	cloud[N - 1][1] = 1;
	cloud[N - 1][2] = 1;
	cloud[N][1] = 1;
	cloud[N][2] = 1;
	V.push_back({ N - 1 ,1 });
	V.push_back({ N - 1 ,2 });
	V.push_back({ N ,1 });
	V.push_back({ N ,2 });
}


void move_cloud(int d, int s)
{
	// 0, 1←, 2↖, 3↑, 4↗, 5→, 6↘, 7↓, 8↙ 
	int dir_x[9] = { 0, 0, -1, -1, -1,  0,  1, 1, 1 };
	int dir_y[9] = { 0, -1, -1, 0,  1,  1, 1, 0, -1 };
	memset(tmp_move, 0, sizeof(tmp_move));
	T.clear();

	for (_st v : V) {
		int nx = v.x + dir_x[d] * s;
		nx %= N;
		if (nx < 1) nx += N;
		
		int ny = v.y + dir_y[d] * s;
		ny %= N;
		if (ny < 1) ny += N;

		//printf("%d %d %d %d %d %d \n", v.x, v.y, dir_x[d] * s, dir_y[d] * s, nx, ny);
		T.push_back({ nx, ny });
		tmp_move[nx][ny] = 1;
	}
	memcpy(cloud, tmp_move, sizeof(tmp_move));
	V.clear();
	
	V = T;
}


void rain()
{
	for (_st v : V) {
		A[v.x][v.y] += 1;
	}
}


void cpy_bug_magic()
{
	int dir_x[4] = { -1, -1, 1, 1 };
	int dir_y[4] = { -1, 1, -1, 1 };

	memset(tmp_magic, 0, sizeof(tmp_magic));

	// 물의 양 증가 
	for (_st v : V) {
		int cnt = 0;
		for (int p = 0; p < 4; p++) {
			int nx = v.x + dir_x[p];
			int ny = v.y + dir_y[p];

			if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
			if (A[nx][ny]) cnt++;
		}
		tmp_magic[v.x][v.y] = cnt;
	}

	// 적용
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (tmp_magic[i][j] == 0) continue;
			A[i][j] += tmp_magic[i][j];
		}
	}
}


void make_cloud()
{
	V.clear();
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (cloud[i][j]) continue;
			if (A[i][j] >= 2) {
				V.push_back({ i, j });
				A[i][j] -= 2;
			}
		}
	}
	memset(cloud, 0, sizeof(cloud));
}


void simul()
{
	for (int m = 0; m < M; m++) {
		move_cloud(CMD[m][0], CMD[m][1]);
		rain();
		// 3. 구름 사라짐 -> cloud, V 재활용 할것임 
		cpy_bug_magic();
		make_cloud();
	}
}


int ouput()
{
	int total = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			total += A[i][j];
		}
	}
	return total;
}


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

실수했던 부분들... 

1. 방향 벡터 만들 때 콤마(,) 가 아니라 온점(.)이 들어갔었다. 발견했으니 다행이지.. 잘 눈에 띄지 않으니까 제발 만들 때 부터 잘 만들자 

2. 이동 시에 nx %= N, ny %= N 이 부분을 nx, ny가 N보다 클 때만 적용해줬다. 그러다 보니까 음수인데 절대값이 N보다 클 경우 구름이 움직이지 못하는 불상사가... (예제 테케 3번) 따라서 일단 새로운 좌표 nx, ny를 구한 후 무조건 N으로 나눈 나머지를 구하고 그 값이 1보다 작을 때만 N을 더해주었다. 

이거 테케 없었으면 어쩔뻔.. 이런거 생각좀 하고 코드 짜자.. 

 

그 외에는 tmp 배열 재활용 할 수 있었지만 혹시나 디버깅을 위해서 따로 만들어주었다. 맵 사이즈도 그렇게 크지 않아서 메모리 별로 안잡아먹은 것 같다. 

맵 탐색 줄이려고 구름 좌표를 벡터에 담아서 관리했는데, 막상 제출하고 보니 이전에 모든 정보를 맵으로 관리한 코드(아래 더보기)와 실행 시간은 별 차이 없더라.. 이것도 맵 사이즈가 작아서 그런감... 

아무튼 안전하고 디버깅 하기 쉬운 방법으로 코드를 짜야겠다고 한 번 더 결심...  

---

이전에 짠 코드는 다음과 같다. 

#include <cstdio>
#include <algorithm>
int N, M;
int A[50 + 2][50 + 2];
int S[50 + 2][50 + 2];	// 구름이 생긴 곳에 물의 양이 1 증가함 

int cloud[50 + 2][50 + 2];
int C[50 + 2][50 + 2];	// 구름이 생김 


// 0  1←, 2↖, 3↑, 4↗, 5→, 6↘, 7↓, 8↙
int dir_x[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};
int dir_y[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1};


struct _st
{
	int d, s;
}Cmd[100 + 2];

void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &A[i][j]);
		}
	}
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &Cmd[i].d, &Cmd[i].s);
	}

	cloud[N - 1][0] = 1;
	cloud[N - 1][1] = 1;
	cloud[N - 2][0] = 1;
	cloud[N - 2][1] = 1;
}


void move_cloud(int m)
{
	// 초기화
	std::fill(&C[0][0], &C[0][0] + sizeof(C) / sizeof(int), 0);
	std::fill(&S[0][0], &S[0][0] + sizeof(S) / sizeof(int), 0);


	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (cloud[i][j]) {
				int ni = i + (Cmd[m].s % N) * (dir_x[Cmd[m].d]);
				int nj = j + (Cmd[m].s % N) * (dir_y[Cmd[m].d]);
				if (ni < 0) ni += N;
				else if (ni > N - 1) ni -= N;
				if (nj < 0) nj += N;
				else if (nj > N - 1) nj -= N;
				//printf("[%d %d] %d %d\n", Cmd[m].d, Cmd[m].s % N, ni, nj);
				C[ni][nj] = -1;		// 구름이 생긴 곳 표시 
				S[ni][nj] = -1;		// 구름이 생긴 곳에 비가 내림 
				A[ni][nj] += 1;		// 구름이 생긴 곳에 물의 양이 1 증가
			}
		}
	}
}


int chk_bucket(int x, int y)
{
	int cnt = 0;
	
	for (int p = 2; p <= 8; p += 2) {
		if (p == 10) p = 2;
		int nx = x + dir_x[p];
		int ny = y + dir_y[p];

		if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
		if (A[nx][ny]) cnt++;
	}
	return cnt;
}



void cp_rain()
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (S[i][j] == -1) {
				int add = chk_bucket(i, j);
				S[i][j] = add;
			}
		}
	}
}


void make_cloud()
{
	// 초기화
	std::fill(&cloud[0][0], &cloud[0][0] + sizeof(cloud) / sizeof(int), 0);
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (S[i][j] == 0) continue;
			A[i][j] += S[i][j];
		}
	}
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (C[i][j] == -1) continue;
			if (A[i][j] >= 2) {
				cloud[i][j] = 1;
				A[i][j] -= 2;
			}
		}
	}
}



void simul()
{
	for (int m = 0; m < M; m++) {
		move_cloud(m);	// 1. 2. 3.
		cp_rain();
		make_cloud();
	}
}


int output()
{
	int total = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (!A[i][j]) continue;
			total += A[i][j];
		}
	}
	return total;
}


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

어떤 상태가 "동시에" 발전할 때는 원본 맵이 아니라 새로운 맵 하나를 더 생성하여 그곳에 상태를 저장하고, 나중에 memcpy 혹은 발전된 상태들만 원본 맵에 옮기는 작업이 필요하다. 

 

이렇게 기존에 제공한 정보 이외에 새로운 정보를 저장할 때는 원본 맵을 더럽히지 말고 새로운 맵을 생성하는 것이 좋다.