17144번 미세먼지 안녕!

17144번: 미세먼지 안녕!

비교적 풀이과정이 스무스했던 문제.

 

문제를 풀기 위해 특별히 알아야 할 알고리즘도 없다. 굳이 분류하자면 시뮬레이션..?

 

이 문제를 크게 두 부분으로 나누자면

 

1. 미세먼지 퍼뜨리기

2. 공기청정기로 공기 순환하기

 

1번에는 함정이 있다. 

 

본인은 2중 for문으로 2차원 배열을 하나씩 체크하며 사방으로 먼지를 퍼뜨리는 방법을 생각했지만

 

문제에서 미세먼지는 모든 칸이 동시에 퍼진다.

 

2차원 배열로 차례차례 먼지를 퍼뜨릴 경우 발생할 수 있는 문제는

 

기준배열에 인접한(먼지가 퍼질 예정인) 인접 배열의 값이 5 미만이어서

 

원래 그 인접 배열의 먼지는 퍼지면 안되지만(5미만의 값은 /5하면 0이므로)

 

기준배열의 먼지가 퍼진 후로 5 이상이 되어 먼지를 퍼뜨릴 자격을 갖게 되어버리는 것이다. 

 

2번은 노가다성으로 대충 해결했다.

 

인덱스 범위를 조절하느라 좀 진땀 뺐다.

 

#include <iostream>
#include <deque>
#include <cstdio>
using namespace std;

int R, C, T;
int map[51][51][2];
int temp[51][51];
int dir_x[4] = { -1,0,1,0 };
int dir_y[4] = { 0,1,0,-1 };
pair<int, int> p1;
pair<int, int> p2;
deque<int> vec[4];
int result;

void print() {//디버깅
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			printf("%3d ", map[i][j][0]);
		}
		cout << '\n';
	}
	cout << '\n';
	/*
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			printf("%3d ", map[i][j][1]);
		}
		cout << '\n';
	}
	cout << '\n';
	*/
}

void spread(int x, int y) {//먼지 퍼뜨리기
	int minus = map[x][y][0] / 5;
	for (int i = 0; i < 4; i++) {
		int add_x = x + dir_x[i];
		int add_y = y + dir_y[i];
		
		if (0 <= add_x && add_x < R && 0 <= add_y && add_y < C) {
			if (map[add_x][add_y][0] != -1) {
				temp[add_x][add_y] += minus;
				map[x][y][0] -= minus;
			}
		}
	}
}

void wind() {//공기순환
	for (int i = 0; i < 4; i++)
		vec[i].clear();
	for (int i = 1; i < C-1; i++) 
		vec[0].push_back(map[p1.first][i][0]);
	for (int i = p1.first; i > 0; i--)
		vec[1].push_back(map[i][C - 1][0]);
	for (int i = C - 1; i > 0; i--)
		vec[2].push_back(map[0][i][0]);
	for (int i = 0; i < p1.first; i++)
		vec[3].push_back(map[i][0][0]);
	map[p1.first][1][0] = 0;

	for (int i = 2; i < C; i++) {
		map[p1.first][i][0] = vec[0].front();
		vec[0].pop_front();
	}
	for (int i = p1.first-1; i >= 0; i--) {
		map[i][C - 1][0] = vec[1].front();
		vec[1].pop_front();
	}
	for (int i = C - 2; i >= 0; i--) {
		map[0][i][0] = vec[2].front();
		vec[2].pop_front();
	}
	for (int i = 1; i <= p1.first; i++) {
		map[i][0][0] = vec[3].front();
		vec[3].pop_front();
	}
	map[p1.first][p1.second][0] = -1;

	for (int i = 0; i < 4; i++)
		vec[i].clear();
	for (int i = 1; i < C - 1; i++)
		vec[0].push_back(map[p2.first][i][0]);
	for (int i = p2.first; i < R - 1; i++)
		vec[1].push_back(map[i][C - 1][0]);
	for (int i = C - 1; i > 0; i--)
		vec[2].push_back(map[R-1][i][0]);
	for (int i = R - 1; i > p2.first; i--)
		vec[3].push_back(map[i][0][0]);
	map[p2.first][1][0] = 0;

	for (int i = 2; i < C; i++) {
		map[p2.first][i][0] = vec[0].front();
		vec[0].pop_front();
	}
	for (int i = p2.first + 1; i < R; i++) {
		map[i][C - 1][0] = vec[1].front();
		vec[1].pop_front();
	}
	for (int i = C - 2; i >= 0; i--) {
		map[R-1][i][0] = vec[2].front();
		vec[2].pop_front();
	}
	for (int i = R-2; i >= p2.first; i--) {
		map[i][0][0] = vec[3].front();
		vec[3].pop_front();
	}
	map[p2.first][p2.second][0] = -1;
}

int main() {
	cin >> R >> C >> T;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> map[i][j][0];
			if (map[i][j][0] > 0)map[i][j][1] = 1;
			if (map[i][j][0] == -1) p2 = make_pair(i, j);
		}
	}
	p1 = make_pair(p2.first - 1, p2.second);

	for (int i = 0; i < T; i++) {
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				map[i][j][1] = 0;
				temp[i][j] = 0;
			}
		}
		for (int j = 0; j < R; j++) {
			for (int k = 0; k < C; k++) {
				if (map[j][k][0] > 0)map[j][k][1] = 1;
			}
		}
		for (int j = 0; j < R; j++) {
			for (int k = 0; k < C; k++) {
				if (map[j][k][1] == 1) {
					spread(j, k);
				}
			}
		}
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				map[i][j][0] += temp[i][j];
			}
		}
		wind();
	}


	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if(map[i][j][0]>0)result += map[i][j][0];
		}
	}
	cout << result;
	return 0;
}