[Baekjoon] 17144번: 미세먼지 안녕!

🥅 문제

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

 

🔍 설계

확산, 반시계 순환, 시계 순환을 각각 구현하면 된다.

 

먼저, 확산을 설계해보았다. 확산은 동시에 일어나기 때문에, 기존 벡터에서 진행하면 안된다.

 

예를 들어, 0행 0열에서 확산이 일어났고, 확산된 양을 0행 1열에 추가하면, 0행 1열에서 확산이 일어날 때, 더해진 양을 고려한 미세먼지의 양으로 확산이 일어난다. 따라서, 확산과 관련된 연산은 before_spread에서 하고, 확산되는 양과 남은 양을 저장하기 위해 after_spread를 만들었다.

 

확산되는 양의 총합을 구하기 위해 확산되는 위치에서 더하는 것은 잘했으나, 남은 양을 저장하는 데 있어서 =으로 처리해서 문제가 있었다. =으로 처리할 경우, 확산되는 양이 저장되었을 때, 그 값이 무시될 수 있다. 따라서 , 확산되는 양을 저장할 때도 +를 해주어야 한다.

 

반시계, 시계 순환은 화살표의 끝부터 시작점까지 천천히 하면, 쉽게 구현할 수 있다.

 

👊 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int r, c, t, spread_amount, result = 0;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
vector<vector<int>> before_spread(50, vector<int>(50));
vector<vector<int>> after_spread(50, vector<int>(50));
vector<int> vacuum_row;

void spread() {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			after_spread[i][j] += before_spread[i][j];
			if (before_spread[i][j] == -1) {
				continue;
			}
			spread_amount = before_spread[i][j] / 5;
			for (int k = 0; k < 4; k++) {
				int new_x = i + dx[k];
				int new_y = j + dy[k];
				if ((new_x >= 0 && new_x < r && new_y >= 0 && new_y < c) && before_spread[new_x][new_y] != -1) {
					after_spread[i][j] -= spread_amount;
					after_spread[new_x][new_y] += spread_amount;
				}
			}
			
		}
	}
	before_spread = after_spread;
	after_spread = vector<vector<int>>(50, vector<int>(50));
}

void clockwise() {
	for (int i = vacuum_row[1] + 1; i < r - 1; i++) {
		before_spread[i][0] = before_spread[i + 1][0];
	}
	for (int i = 0; i < c - 1; i++) {
		before_spread[r - 1][i] = before_spread[r - 1][i + 1];
	}
	for (int i = r - 1; i > vacuum_row[1]; i--) {
		before_spread[i][c - 1] = before_spread[i - 1][c - 1];
	}
	for (int i = c - 1; i > 1; i--) {
		before_spread[vacuum_row[1]][i] = before_spread[vacuum_row[1]][i - 1];
	}

	before_spread[vacuum_row[1]][1] = 0;
}

void anti_clockwise() {
	for (int i = vacuum_row[0] - 1; i > 0; i--) {
		before_spread[i][0] = before_spread[i - 1][0];
	}
	for (int i = 0; i < c - 1; i++) {
		before_spread[0][i] = before_spread[0][i + 1];
	}
	for (int i = 0; i < vacuum_row[0]; i++) {
		before_spread[i][c - 1] = before_spread[i + 1][c - 1];
	}
	for (int i = c - 1; i > 1; i--) {
		before_spread[vacuum_row[0]][i] = before_spread[vacuum_row[0]][i - 1];
	}
	before_spread[vacuum_row[0]][1] = 0;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);	
	cin >> r >> c >> t;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> before_spread[i][j];
			if (before_spread[i][j] == -1) {
				vacuum_row.push_back(i);
			}
		}
	}

	for (int i = 0; i < t; i++) {
		spread();
		anti_clockwise();
		clockwise();
	}
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			result += before_spread[i][j];
		}
	}
	result += 2;
	cout << result << "\n";

	return 0;
}