백준 17144번 미세먼지 안녕! C++

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

 

문제에 써있는대로 구현하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int r, c, t;

vector<pair<int, int>> airCleaner(2);

int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };

void SpreadDust(vector<vector<int>>& board) {
	vector<vector<int>> tmp(r, vector<int>(c, 0));
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (board[i][j] == 0) continue;
			int spreadAmount = board[i][j] / 5;
			int cnt = 0;
			for (int k = 0; k < 4; k++) {
				int nextRow = i + dRow[k];
				int nextCol = j + dCol[k];
				if (nextRow < 0 || nextRow >= r) continue;
				if (nextCol < 0 || nextCol >= c) continue;
				if (board[nextRow][nextCol] == -1) continue;
				tmp[nextRow][nextCol] += spreadAmount;
				cnt++;
			}
			tmp[i][j] -= spreadAmount * cnt;
		}
	}
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			board[i][j] += tmp[i][j];
		}
	}
}

void WorkAirCleaner(vector<vector<int>>& board) {
	for (int i = 0; i < 2; i++) {
		int dir;
		int maxRow = r - 1;
		int minRow = 0;
		if (i == 0) {
			dir = 0;
			maxRow = airCleaner[i].first;
		}
		else {
			dir = 2;
			minRow = airCleaner[i].first;
		}

		int currRow = airCleaner[i].first + dRow[dir];
		int currCol = airCleaner[i].second + dCol[dir];
		while (currRow != airCleaner[i].first || currCol != airCleaner[i].second) {
			int revDir = (dir + 2) % 4;
			int lastRow = currRow + dRow[revDir];
			int lastCol = currCol + dCol[revDir];
			if (board[lastRow][lastCol] == 0) {
				board[lastRow][lastCol] = board[currRow][currCol];
			}
			board[currRow][currCol] = 0;
			int nextRow = currRow + dRow[dir];
			int nextCol = currCol + dCol[dir];
			if (nextRow < minRow || nextRow > maxRow || nextCol < 0 || nextCol >= c) {
				if (i == 0) dir = (dir + 1) % 4;
				else dir = (dir + 3) % 4;
				nextRow = currRow + dRow[dir];
				nextCol = currCol + dCol[dir];
			}
			currRow = nextRow;
			currCol = nextCol;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> r >> c >> t;
	vector<vector<int>> board(r, vector<int>(c));
	int num = 0;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> board[i][j];
			if (board[i][j] == -1) {
				airCleaner[num] = { i,j };
				num++;
			}
		}
	}
	for (int i = 0; i < t; i++) {
		SpreadDust(board);
		WorkAirCleaner(board);
	}
	int ans = 0;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (board[i][j] == -1) continue;
			ans += board[i][j];
		}
	}
	cout << ans;
};