[BOJ][17144] 미세먼지 안녕!

문제

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

17144번: 미세먼지 안녕!

풀이

크게 두 가지를 반복합니다.

첫번째는 먼지를 사방으로 퍼트리기, 두번째는 공기청정기를 가동하는 것입니다.

1. 먼지 퍼뜨리기

먼지가 퍼질 수 있는 방향의 갯수를 체크한 뒤, 퍼지는 것이 가능하면 먼지를 퍼뜨리는 순서로 진행했습니다. 이 때, 먼지가 모두 동시에 퍼져야 하기 때문에 smap에 퍼지는 갯수를 적어주도록 합니다.

 1) 먼지가 몇 방향으로 퍼질 수 있는지 체크

 2) 먼지의 갯수가 퍼질 수 있는지 여부 체크

 3) 먼지 퍼뜨리기(smap), 현재 위치의 먼지 갯수 줄이기, 두개의 map에 있는 먼지 합치기

2. 공기청정기 돌리기

두 개의 공기청정기가 각각 다른 방향으로 순환하므로  방향 체크를 잘 해주어야 하는 부분이라고 생각합니다.

 1)공기청정기의 위치를 미리 넣어준 뒤, 

 2)퍼진 먼지의 값을 시계방향, 반시계 방향으로 움직여줍니다.

 3) a b c d e 순으로 먼지가 있고 a->e방향으로 움직여야 한다면  b=a, c=b ... 순으로 헷갈리지 않게 넣어주도록 합니다.

코드

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
int r, c, t;
int map[1001][1001];
int smap[1001][1001];
vector<pair<int,int>> cleaner;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
void spread() {
	memset(smap, 0, sizeof(smap));
	for (int x = 0; x < r; x++) {
		for (int y = 0; y < c; y++) {


			int munzi = map[x][y] / 5; //먼지 갯수
			int dir_num = 0;
			//퍼지는 방향 갯수 체크
			if (map[x][y] == 0) continue;
			for (int p = 0; p < 4; p++) {
				int nx = x + dx[p];
				int ny = y + dy[p];
				if (nx < 0 || ny < 0 || nx >= r || ny >= c || map[nx][ny]==-1) continue;
				//먼지 갯수 가능한지 체크
				dir_num++;
			}

			if (map[x][y] >= dir_num * munzi) {
				for (int p = 0; p < 4; p++) {
					int nx = x + dx[p];
					int ny = y + dy[p];
					if (nx < 0 || ny < 0 || nx >= r || ny >= c || map[nx][ny] == -1) continue;
					//먼지 갯수 가능한지 체크
					smap[nx][ny] += munzi;
					map[x][y] -= munzi;
				}
			}
		}
	}
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			map[i][j] += smap[i][j];
		}
	}
	//printf("---------------------\n");
	//for (int i = 0; i < r; i++) {
	//	for (int j = 0; j < c; j++) {
	//		cout << map[i][j] << ' ';
	//	}
	//	cout << '\n';
	//}
}
void cleaning() {
	int first_x = cleaner[0].first;
	int first_y = cleaner[0].second;
	int second_x = cleaner[1].first;
	int second_y = cleaner[1].second;
	//좌
	for (int i = first_x - 1; i > 0; i--) {
		map[i][0] = map[i - 1][0];
	}
	//상
	for (int i = 0; i < c - 1; i++) {
		map[0][i] = map[0][i + 1];
	}
	//우
	for (int i = 0; i < first_x; i++) {
		map[i][c - 1] = map[i + 1][c - 1];
	}
	//하
	for (int i = c - 1; i > 0; i--) {
		map[first_x][i] = map[first_x][i - 1];
	}
	map[first_x][1] = 0;

	//좌
	for (int i = second_x + 1; i < r - 1; i++) {
		map[i][0] = map[i + 1][0];
	}
	//하
	for (int i = 0; i < c - 1; i++) {
		map[r - 1][i] = map[r - 1][i + 1];
	}
	//우
	for (int i = r - 1; i > second_x; i--) {
		map[i][c - 1] = map[i - 1][c - 1];
	}
	//상
	for (int i = c - 1; i > 0; i--) {
		map[second_x][i] = map[second_x][i - 1];
	}
	map[second_x][1] = 0;
	//printf("---------------------\n");
	//for (int i = 0; i < r; i++) {
	//	for (int j = 0; j < c; j++) {
	//		cout << map[i][j] << ' ';
	//	}
	//	cout << '\n';
	//}
}
int main() {
	int T;
	cin >> r >> c >> T;
	memset(map, 0, sizeof(map));
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> map[i][j];
			if (map[i][j] == -1) cleaner.push_back(make_pair(i, j));
		}
	}

	for (int t = 0; t < T; t++) {
		spread();
		cleaning();
	}
	int res = 0;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (map[i][j] == -1) continue;
			res += map[i][j];
		}
	}
	cout << res << '\n';
}