[ boj : 21610 ] 마법사 상어와 비바라기

www.acmicpc.net/problem/21610

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

문제 : "문제가 넘나 복잡하여 그냥 생략하겠습니다. 디스크립션 꼼꼼하게 읽으세요"

 

해설 : 2021 상반기 삼성 문제입니다.

전형적인 빡구현 문제인데 솔직히 삼성문제 치고 굉장히 쉽게 나온 문제인 것 같습니다. 만약 실제 시험장에서 치셨더라면 아무리 못해도 1시간 안에 클리어 해주셔야지 2번째 문제로 무난하게 넘어갈 것 같네요.

(화이팅 입니다 모두들!!!!!힘냅시다)

 

먼저 주어진 조건들을 정리해 봅시다.

구름의 위치를 담을 수 있는 큐, 사라지는 구름의 위치를 담는 큐 , 이 구름들이 비를 내리고 사라졌을때 흔적을 남겨야 되는 배열 , 8방향의 좌표를 나타낼수 있는 변수 

이정도를 생각해 두고 차근차근 구현하면 됩니다.

 

1. 이동할 구름의 위치를 담을 수 있는 큐에 좌표들을 삽입해 줍니다.

2. 큐에서 하나씩 빼서 방향에 맞게 이동시켜 줍시다. 이때 현재 들어있는 큐의 사이즈만큼만 pop을 해주세요.

그리고 비를 내립시다 +1

3. 구름을 사라지게 하는데 이때 사라진 구름의 위치는 후에 물복사마법을 실행하니 이 좌표들을 담을 수 있는 큐를 선언해서 여기에 담아줍니다. 또한, 나중에 구름이 생성될 때 제외되니 배열에 이를 체크해 줍시다.

4. 구름이 사라지면서 대각선 방향에 물복사마법을 실행합니다.

5. 물의 양이 2 이상인 좌표들을 큐에 삽입합니다.

 

이것을 반복해 줍니다.

#include<bits/stdc++.h>

using namespace std;

int board[51][51],check[51][51];

int n, m;
vector<pair<int, int>> order;
queue<pair<int, int>> q,sq;

int dx[] = { 0,-1,-1,-1,0,1,1,1 };
int dy[] = { -1,-1,0,1,1,1,0,-1 };

int get_ans();
void move_cloud(pair<int, int> pr);
void duplicate_magic();
void make_cloud();
void init();
void input();

void show();

int main()
{
	input();
	for (int i = 0; i < order.size(); i++) {
		move_cloud(order[i]);
		//show();
		//cout << "\n";
	}
	cout << get_ans();
	return 0;
}
void show()
{
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			cout << board[i][j] << " ";
		cout << "\n";
	}
}
int get_ans()
{
	int sum = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			sum += board[i][j];
	return sum;
}
//구름의 이동
void move_cloud(pair<int,int> pr)
{	
	int size=q.size();
	for (int i = 0; i < size; i++) {
		pair<int, int> cur = q.front();
		q.pop();

		int tx=cur.first, ty=cur.second;
		for (int s = 0; s < pr.second; s++) {
			tx += dx[pr.first];
			ty += dy[pr.first];

			if (tx <= 0)tx = n;
			if (ty <= 0)ty = n;
			if (tx > n)tx = 1;
			if (ty > n)ty = 1;
		}
		q.push({ tx,ty });
	}
	sq = q;
	//구름에 있는 칸에 비 1씩
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();

		//구름 체크
		check[cur.first][cur.second] = 1;
		//비가 1씩
		board[cur.first][cur.second] += 1;
	}
	duplicate_magic();
	make_cloud();
	init();
}
//물복사마법
void duplicate_magic()
{
	while (!sq.empty()) {
		pair<int, int> cur = sq.front();
		sq.pop();
		for (int i = 1; i < 8; i += 2) {
			int tx = cur.first + dx[i];
			int ty = cur.second + dy[i];

			if (tx <= 0 || tx > n || ty <= 0 || ty > n)continue;

			if (board[tx][ty] > 0)
				board[cur.first][cur.second] += 1;
		}
	}
}
//구름 생성
void make_cloud()
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (!check[i][j] && board[i][j] >= 2) {
				q.push({ i,j });
				board[i][j] -= 2;
			}
}
void init()
{
	memset(check, 0, sizeof(check));
}
void input()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> board[i][j];
	int x, y;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		order.push_back({ x-1,y });
	}
	q.push({ n,1 });
	q.push({ n,2 });
	q.push({ n - 1,1 });
	q.push({ n - 1,2 });
}