[백준/BOJ] 17144번 미세먼지 안녕! (C++)

www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

삼성 역량 테스트 기출 문제 : 시뮬레이션(구현) (다시 풀기)

먼지의 확산을 구현하고, 공기청정기의 작동을 구현하면 되는 문제입니다. 이때 주의해야 할 점은 먼지의 확산을 구현하는 과정에서, 2차원 배열이 하나만 존재하면 올바른 확산을 구현할 수 없기 때문에 두 개의 배열이 필요합니다. 공기청정기의 작동은 다음과 같은 접근으로 구현했습니다.

 

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

위 공기청정기, 아래 공기청정기를 기준으로 가까운쪽에서 시작하여, 각각의 변마다 한칸씩 값을 땡겨오는 것입니다. 이렇게 하면 변수를 선언해서 swap 작업을 해주지 않아도 공기청정기의 작동을 구현할 수 있습니다.

 

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

int R, C, T;
int map[2][51][51]; // cur, next
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<pair<int, int > > cleaner;

void move(int cur) {
	int ucx = cleaner[0].first, ucy = cleaner[0].second; // 위의 공기청정기 좌표 
	int dcx = cleaner[1].first, dcy = cleaner[1].second; // 아래의 공기청정기 좌표 
	
	// 위 공기청정기의 작동 
	for(int x = ucx - 1; x > 0; x--) {
		map[cur][x][0] = map[cur][x - 1][0];
	}
	for(int y = 0; y < C - 1; y++) {
		map[cur][0][y] = map[cur][0][y + 1];
	}
	for(int x = 0; x < ucx; x++) {
		map[cur][x][C - 1] = map[cur][x + 1][C - 1]; 
	}
	for(int y = C - 1; y > ucy; y--) {
		map[cur][ucx][y] = map[cur][ucx][y - 1];
	}
	
	map[cur][ucx][1] = 0;
	
	// 아래 공기청정기의 작동
	for(int x = dcx + 1; x < R - 1; x++) {
		map[cur][x][0] = map[cur][x + 1][0];
	} 
	
	for(int y = 0; y < C - 1; y++) {
		map[cur][R - 1][y] = map[cur][R - 1][y + 1];
	}
	
	for(int x = R - 1; x > dcx; x--) {
		map[cur][x][C - 1] = map[cur][x - 1][C - 1];
	}
	
	for(int y = C - 1; y > dcy; y--) {
		map[cur][dcx][y] = map[cur][dcx][y - 1];
	}
	
	map[cur][dcx][1] = 0;
}

void spread(int cur) {
	int next = (cur + 1) % 2;
	for(int i = 0; i < R; i++) {
		for(int j = 0; j < C; j++) {
			if(map[cur][i][j] == -1) map[next][i][j] == -1;
			else map[next][i][j] = 0;
		}
	}
	
	for(int i = 0; i < R; i++) {
		for(int j = 0; j < C; j++) {
			if(map[next][i][j] != -1) {
				int sum = 0;
				for(int k = 0; k < 4; k++) {
					int nx = i + dx[k];
					int ny = j + dy[k];
					if(map[cur][nx][ny] == -1 || nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
					map[next][nx][ny] += (map[cur][i][j]) / 5;
					sum += (map[cur][i][j]) / 5;
				}
			 	map[next][i][j] += map[cur][i][j] - sum; 
			}
		}
	}
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> R >> C >> T;
    for(int i = 0; i < R; i++) {
    	for(int j = 0; j < C; j++) {
    		cin >> map[0][i][j];
    		if(map[0][i][j] == -1) cleaner.push_back({ i, j });
		}
	}
	
	int cur = 0;
	while(T--) {	
		spread(cur); // cur -> next
		cur = (cur + 1) % 2; // next -> cur
		move(cur);
	}	
	
	int answer = 0;
	for(int i = 0; i < R; i++) {
		for(int j = 0; j < C; j++) {
			if(map[cur][i][j] > 0) answer += map[cur][i][j];
		}
	}
	
	cout << answer;
}