(c++)백준 21610번: 마법사 상어와 비바라기

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

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

[풀이]

구현한 것(함수)

1. 구름 이동 함수 (d와 s를 받는 즉시 호출) s는 s%N으로 최소화하여 움직이는 시간 줄이기

2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 물+1 함수

*문제에서는 이 다음에 구름이 사라지지만, 구현할 때는 다음 함수에서 사용하기 위해 구름 위치 정보를 남겨둠

3. 물복사버그 함수 -> 구름 위치 정보 삭제(p_Cloud)

4.  bool Cloud[][]배열에 이전에 구름이 있었던 위치 저장해놓았으므로, c_Cloud[][]에 복사하고, 이전에 구름이 없었고, 물의 양이 2 이상인 모든 칸에 구름 새로 생김 -> 구름 위치정보(p_Cloud), Cloud[][]에 표시

 

[코드]

#include <iostream>
#include <deque>
#include <cstring>//memset
using namespace std;

struct Pos {
	int x, y;
};

int N, M;
int A[51][51];
bool Cloud[51][51];
bool c_Cloud[51][51];
deque<Pos>p_Cloud;//구름 위치
const int dxy[][2] = { {0,0},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1} };

//d방향으로 s칸만큼 구름 이동
void MoveCloud(int d, int s) {
	memset(Cloud, false, sizeof(Cloud));
	int cloud_cnt = p_Cloud.size();
	for (int i = 0; i < cloud_cnt; i++) {
		int x = p_Cloud.front().x;
		int y = p_Cloud.front().y;
		p_Cloud.pop_front();
		//실제 이동하는 칸
		int rs = s % N;
		while (rs--) {
			x += dxy[d][0];
			y += dxy[d][1];
			if (x > N)
				x = 1;
			else if (x <= 0)
				x = N;
			if (y > N)
				y = 1;
			else if (y <= 0)
				y = N;
		}
		p_Cloud.push_back({ x,y });
		Cloud[x][y] = true;
	}
}

//각 구름에서 비가 내려 구름이 있는 칸 바구니에 물+1
void Rain() {
	int cloud_cnt = p_Cloud.size();
	for (int i = 0; i < cloud_cnt; i++) {
		int x = p_Cloud[i].x;
		int y = p_Cloud[i].y;
		A[x][y]++;
	}
}

//물복사 버그 : 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r,c)에 있는 바구니의 물의 양이 증가
void Copy() {
	int cloud_cnt = p_Cloud.size();
	for (int i = 0; i < cloud_cnt; i++) {
		int x = p_Cloud[i].x;
		int y = p_Cloud[i].y;
		int water_cnt = 0;
		for (int d = 2; d <= 8; d += 2) {
			int nx = x + dxy[d][0];
			int ny = y + dxy[d][1];
			//범위 벗어나면 continue
			if (nx <= 0 || nx > N || ny <= 0 || ny > N)
				continue;
			if (A[nx][ny] > 0)
				water_cnt++;
		}
		A[x][y] += water_cnt;
	}
	//구름 사라지기
	p_Cloud.clear();
}

//방금 구름 사라진 칸 제외 물의 양이 2 이상인 모든 칸에 구름이 생김
void makeCloud() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			c_Cloud[i][j] = Cloud[i][j];
			Cloud[i][j] = false;
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (A[i][j] >= 2 && c_Cloud[i][j] == false) {
				p_Cloud.push_back({ i,j });
				Cloud[i][j] = true;
				A[i][j] -= 2;
			}
		}
	}
}

int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> A[i][j];
		}
	}
	//초기 구름
	p_Cloud.push_back({ N,1 });
	p_Cloud.push_back({ N,2 });
	p_Cloud.push_back({ N - 1,1 });
	p_Cloud.push_back({ N - 1,2 });

	int d, s;

	for (int i = 0; i < M; i++) {
		cin >> d >> s;
		MoveCloud(d, s);
		Rain();
		Copy();
		makeCloud();
		/*
		cout << '\n';
		for (int x = 1; x <= N; x++) {
			for (int y = 1; y <= N; y++) {
				cout << A[x][y] << ' ';
			}
			cout << '\n';
		}
		cout << '\n';
		*/
	}
	int answer = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			answer += A[i][j];
		}
	}
	cout << answer << '\n';
	return 0;
}