[삼성 17144] 미세먼지 안녕!

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

문제설명

1. r * c의 칸으로 구성된 방에서 미세먼지와 공기청정기가 있다.
2. 미세먼지는 1초마다 상하좌우 칸으로 확산된다.

• 확산되는 양은 Ar,c/5이고 소수점은 버린다.
• (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.

3. 공기청정기는 첫번째 열 행 2칸을 차지하며 1초마다 바람을 순환시킨다.
   (먼지들이 윗 바람에 의해 반시계방향으로, 아랫 바람에 의해 시계방향으로 한 칸씩 밀린다. 이 때 공기청정기로 유입된 미세먼지는 소멸)

입력

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.

둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

아이디어

50 * 50의 칸에서의 미세먼지의 확산, 공기청정기의 일을 t초간 시뮬레이션 한다.

1초마다 50 * 50 2차원 배열을 다 돌면서 확산시키며, 공기청정기는 해당 방향으로 데이터를 민다.

1. 이 때 1초 내에 다른 칸에서 유입된 먼지가 포함된 데이터를 기준으로 재확산 시키면 안되므로 2차원 배열을 2개 써서 copy했다.

copy(&arr2[0][0], &arr2[0][0] + 50 * 50, &arr[0][0]);

2. 한 칸씩 데이터를 미는 과정은

int fill_out(int v, int i, int j) {
	int t = arr[i][j];
	arr[i][j] = v;
	return t;
}

---

int t = arr[ma.i][1];
	arr[ma.i][1] = 0;
	for (int j = 1; j < c-1; j++) {
		t = fill_out(t, ma.i, j + 1);
	}
	for (int i = ma.i; i >= 1; i--) {
		t = fill_out(t, i-1, c - 1);
	}

소스코드

https://www.acmicpc.net/source/23136896

#include<iostream>
#include<queue>
#include<math.h>
using namespace std;

struct pos {
	int i, j;
	pos(int ii, int jj) {
		i = ii; j = jj;
	}
};

int r, c, t;
int arr[50][50];
int arr2[50][50];
pos ma = pos(-1, -1);

int di[4] = { -1,1,0,0 };
int dj[4] = { 0,0,-1,1 };
int fill_out(int v, int i, int j) {
	int t = arr[i][j];
	arr[i][j] = v;
	return t;
}

void move_baram() {//처음에 바람을 한번 불어둔 상태에서 시작하자
	//그 후 바람의위치가 밀려난 먼지의 위치
	int t = arr[ma.i][1];
	arr[ma.i][1] = 0;
	for (int j = 1; j < c-1; j++) {
		t = fill_out(t, ma.i, j + 1);
	}
	for (int i = ma.i; i >= 1; i--) {
		t = fill_out(t, i-1, c - 1);
	}
	for (int j = c - 1; j >= 1; j--) {
		/*
		if (t == 9) {
			cout << "t는 9 " << 0 << "," << j - 1 << endl;
		}
		*/
		
		t = fill_out(t, 0, j-1);
		/*
		if (j - 1 == 6) {
			cout << "j-1이 6인데" << arr[0][j-1] << endl;
		}
		*/
	}
	for (int i = 0; i <= ma.i; i++) {
		t = fill_out(t, i+1, 0);
	}
	arr[ma.i][0] = -1;
	t = arr[ma.i+1][1];
	arr[ma.i + 1][1] = 0;
	for (int j = 1; j < c - 1; j++) {
		t = fill_out(t, ma.i + 1, j + 1);
	}
	for (int i = ma.i + 1; i < r - 1; i++) {
		t = fill_out(t, i+1, c - 1);
	}
	for (int j = c - 1; j > 1; j--) {
		t = fill_out(t, r-1, j - 1);
	}
	for (int i = r - 1; i > ma.i + 1; i--) {
		t = fill_out(t, i, 0);
	}
	arr[ma.i + 1][0] = -1;
}
bool insertable(pos p) {
	return p.i >= 0 && p.i < r&& p.j >= 0 && p.j < c&& arr[p.i][p.j] != -1;
}
void print_mat(int arr[][50]) {
	cout << "새로운프린트" << endl;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << arr[i][j] << " ";
		}
		cout << endl;
	}
	
}


int main() {
	cin >> r >> c >> t;
	queue<pos> q;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == -1 && ma.i == -1) {
				ma.i = i;
				ma.j = j;
			}
			if (arr[i][j] > 0) {
				q.push(pos(i, j));
			}
		}
	}
	//cout << "입력끗" << endl;
	

	copy(&arr[0][0], &arr[0][0] + 50 * 50, &arr2[0][0]);
	for (int time = 0; time < t; time++) {
		//1초동안 일어나는 일 시뮬레이션
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (arr[i][j] == 0 || arr[i][j] == -1) continue;
				int sd = arr[i][j] / 5;
				for (int ctr = 0; ctr < 4; ctr++) {
					pos c = pos(i + di[ctr], j + dj[ctr]);
					if (insertable(c)) {
						arr2[c.i][c.j] += sd;
						arr2[i][j] -= sd;
					}
				}
			}
		}
		//print_mat(arr2);
		
		copy(&arr2[0][0], &arr2[0][0] + 50 * 50, &arr[0][0]);
		move_baram();
		copy(&arr[0][0], &arr[0][0] + 50 * 50, &arr2[0][0]);
		//print_mat(arr);
	}
	int sum = 0;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (arr[i][j] != -1) {
				sum += arr[i][j];
			}
		}
	}
	cout << sum << endl;
	
	//t 초가 지난 후 이 방에 남아있는 미세먼지의 총량을 출력하자!


}