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

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

17144번: 미세먼지 안녕!

이번에도 구현 문제인데, 문제 자체가 어려운 변수들을 많이 제거한 상태로 출제되었다.

처음에 공기청정기가 위아래 간격이 최소 2칸이 된다는 점을 제대로 안 읽어서 헛발질 할 뻔했다...;;

 

그렇게 전제조건이 깔리면서 일반적인 경우의 수만 풀어내면 된다.

이러한 구현 문제는 실수를 미연에 방지하는 것이 중요하기 때문에 함수를 최대한 패턴화해서 쪼개는 게 중요하다.

 

• 미세먼지의 확산
• 공기청정기의 위쪽 순환
• 공기청정기의 아래쪽 순환

미세먼지의 확산까지는 아래 사항만 주의하면 된다.

흩어진 미세먼지와 기존의 미세먼지를 분리하는 것만 안 헷갈리면 된다. 만약 이를 분리하지 않으면 흩어진 미세먼지를 다시 흩뜨리는 일이 발생하기 때문이다.

 

그런데 순환은 어떻게 시킬까? 처음에는 자연스럽게 화살표 방향 순서대로 옮기면 되지 않을까? 라는 naive한 생각을 할 수 있다.

그러나 코드 구현은 그렇게 만만하지 않다.

정보를 잃지 않고 미세먼지를 한 칸씩 옮기기 위해서는 화살표 반대 방향부터 한칸씩 땡겨야 한다.

이 때 공기청정기가 위치한 곳에 들어오는 미세먼지가 없어지고, 배열의 크기를 알려주는 R,C와 다르게 공기청정기의 위치 인덱스를 알려주는 air_r, below_air_r은 등호를 포함하는 것도 놓쳐선 안된다.

 

그리고 디버깅을 편하게 하기 위해 프린트를 하는 함수를 따로 생성해서 사이사이마다 삽입해서 확인해주었다.

#include <iostream>
#include <vector>
// #pragma warning(disable:4996)

using namespace std;
int R, C, T;
vector<vector<int>> arr(50, vector<int>(50));
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };
int air_r = -1;
bool inside(int r, int c) {
	return r >= 0 && r < R&& c >= 0 && c < C;
}

void print_arr() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cout << arr[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

void spread() {
	vector<vector<int>> arr_cp(50, vector<int>(50, 0));
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (arr[i][j] > 0) {
				int cnt = 0;
				for (int d = 0; d < 4; d++) {
					int nr = i + dr[d];
					int nc = j + dc[d];

					if (inside(nr, nc) && arr[nr][nc] != -1) {
						arr_cp[nr][nc] += arr[i][j] / 5;
						cnt++;
					}
				}
				arr_cp[i][j] -= (arr[i][j] / 5) * cnt;
			}
		}
	}

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			arr[i][j] += arr_cp[i][j];
		}
	}
}

void air() {
	arr[air_r - 1][0] = 0;
	for (int i = air_r - 1; i > 0; i--) {
		arr[i][0] += arr[i - 1][0];
		arr[i - 1][0] = 0;
	}
	
	for (int i = 1; i < C; i++) {
		arr[0][i - 1] += arr[0][i];
		arr[0][i] = 0;
	}

	for (int i = 1; i <= air_r; i++) {
		arr[i - 1][C - 1] += arr[i][C - 1];
		arr[i][C - 1] = 0;
	}

	for (int i = C - 1; i > 1; i--) {
		arr[air_r][i] += arr[air_r][i - 1];
		arr[air_r][i - 1] = 0;
	}

	int below_air_r = air_r + 1;
	arr[below_air_r + 1][0] = 0;
	for (int i = below_air_r + 2; i < R; i++) {
		arr[i - 1][0] += arr[i][0];
		arr[i][0] = 0;
	}

	for (int i = 1; i < C; i++) {
		arr[R - 1][i - 1] += arr[R - 1][i];
		arr[R - 1][i] = 0;
	}

	for (int i = R - 2; i >= below_air_r; i--) {
		arr[i + 1][C - 1] += arr[i][C - 1];
		arr[i][C - 1] = 0;
	}

	for (int i = C - 1; i > 1; i--) {
		arr[below_air_r][i] += arr[below_air_r][i - 1];
		arr[below_air_r][i - 1] = 0;
	}
}

int main() {
	int answer = 0;
	// freopen("input.txt", "r", stdin);
	cin >> R >> C >> T;
	
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> arr[i][j];
			if (j == 0 && arr[i][j] == -1 && air_r == -1) {
				air_r = i;
			}
		}
	}

	while (T--) {
		spread();
		// print_arr();
		air();
		// print_arr();
	}

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (arr[i][j] != -1 && arr[i][j] != 0) {
				answer += arr[i][j];
			}
		}
	}

	cout << answer << '\n';
}