백준 17144 - 미세먼지 안녕!

문제 링크입니다 https://www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

 

미세먼지의 위치와 공기 청정기의 위치가 주어지고 일정 시간이 지난 뒤 남은 미세먼지의 갯수를 구하는 문제입니다.

미세먼지의 확산 방법부터 보겠습니다.

 

미세먼지는 자신이 있는 위치에서 상하좌우로 퍼집니다.(위 사진과 같이 퍼집니다.)

공기 청정기의 순환 방식도 보겠습니다.

화살표를 따라 공기가 움직이고 미세먼지는 공기를 따라 움직입니다. 이때 미세먼지가 공기 청정기 안으로 빨려간다면 없어집니다.

 

미세먼지 퍼짐 -> 공기의 순환 으로 일어나기 때문에 미세먼지가 퍼지는 것부터 구현을 해야합니다.

1. 미세먼지가 있는 곳을 큐에 넣어준 다음 하나씩 확인하면서 상하좌우에 퍼트립니다.

2. 미세먼지가 퍼진 곳의 갯수를 구한 다음 현재 칸에 얼마나 남았는지 저장합니다.

저는 이 방식으로 퍼트렸습니다.

 

공기의 순환의 같은 경우에는

1. 공기 청정기의 위쪽 부분까지 for문을 통해서 움직임을 구현합니다.

2. 공기 청정기의 아래쪽부터 배열의 끝까지 for문을 통해서 움직임을 구현합니다.

3. 미세먼지가 움직이는 중에 공기 청정기 도달하면 없애줍니다.

이 방식으로 공기의 움직임을 구현했습니다.

 

----->위 과정을 시간만큼 반복합니다.

 

자세한 것은 코드를 참고해주세요!

 

#define CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

int R, C, T;
int fine_dust[51][51];
int arr[51][51];
int up[4] = { 0,1,0,-1 };
int down[4] = { 1,0,-1,0 };
int number_dust;
queue<pair<int, int>> dust;
vector<pair<int, int>> air_clean;

void spread() {
	while (!dust.empty()) {
		int x = dust.front().first;
		int y = dust.front().second;
		int num = arr[x][y] / 5;
		int cnt = 0;
		dust.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x + up[i];
			int yy = y + down[i];
			if (xx >= 1 && xx <= R && yy >= 1 && yy <= C &&  arr[xx][yy] != -1) {
				cnt++;
				fine_dust[xx][yy] += num;
			}
		}
		fine_dust[x][y] += (arr[x][y] - cnt * num);
	}
	/*for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cout << fine_dust[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";*/
}

void air_cleaning() {
	int x1 = air_clean[0].first;
	int y1 = air_clean[0].second;
	int x2 = air_clean[1].first;
	int y2 = air_clean[1].second;
	for (int i = 1; i <= x1; i++) {
		for (int j = 1; j <= C; j++) {
			if (i == 1) {
				if (j == 1) {
					if (i + 1 == x1 && j == y1) {
						arr[i + 1][j] = 0;
					}
					else {
						arr[i + 1][j] = fine_dust[i][j];
					}
				}
				else {
					if (i == x1 && j - 1 == y1) {
						arr[i][j - 1] = 0;
					}
					else {
						arr[i][j - 1] = fine_dust[i][j];
					}
				}
			}
			else if (i == x1) {
				if (j == C) {
					if (i - 1 == x1 && j == y1) {
						arr[i - 1][j] = 0;
					}
					else {
						arr[i - 1][j] = fine_dust[i][j];
					}
				}
				else {
					if(i == x1 && j+1 == y1) {
						arr[i][j+1] = 0;
					}
					else {
						arr[i][j+1] = fine_dust[i][j];
					}
				}
			}
			else {
				if (j == 1) {
					if (i + 1 == x1 && j == y1) {
						arr[i + 1][j] = 0;
					}
					else {
						arr[i + 1][j] = fine_dust[i][j];
					}
				}
				else if (j == C) {
					if (i - 1 == x1 && j == y1) {
						arr[i - 1][j] = 0;
					}
					else {
						arr[i - 1][j] = fine_dust[i][j];
					}
				}
				else {
					arr[i][j] = fine_dust[i][j];
				}
			}
		}
	}
	for (int i = x2; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (i == x2) {
				if (j == C) {
					if (i + 1 == x2 && j == y2) {
						arr[i + 1][j] = 0;
					}
					else {
						arr[i + 1][j] = fine_dust[i][j];
					}
				}
				else {
					if (i == x2 && j+1 == y2) {
						arr[i][j+1] = 0;
					}
					else {
						arr[i][j+1] = fine_dust[i][j];
					}
				}
			}
			else if (i == R) {
				if (j == 1) {
					if (i -1 == x2 && j == y2) {
						arr[i - 1][j] = 0;
					}
					else {
						arr[i - 1][j] = fine_dust[i][j];
					}
				}
				else {
					if (i == x2 && j-1 == y2) {
						arr[i][j-1] = 0;
					}
					else {
						arr[i][j-1] = fine_dust[i][j];
					}
				}
			}
			else {
				if (j == 1) {
					if (i - 1 == x2 && j == y2) {
						arr[i - 1][j] = 0;
					}
					else {
						arr[i - 1][j] = fine_dust[i][j];
					}
				}
				else if (j == C) {
					if (i + 1 == x2 && j == y2) {
						arr[i + 1][j] = 0;
					}
					else {
						arr[i + 1][j] = fine_dust[i][j];
					}
				}
				else {
					arr[i][j] = fine_dust[i][j];
				}
			}
		}
	}
	arr[x1][y1] = -1;
	arr[x2][y2] = -1;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			//cout << arr[i][j] << " ";
			fine_dust[i][j] = 0;
			if (arr[i][j] > 0) {
				dust.push(make_pair(i, j));
			}
		}
		//cout << "\n";
	}
}

void solve() {
	for (int i = 0; i < T; i++) {
		spread();
		air_cleaning();
	}
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (arr[i][j] > 0) {
				number_dust+=arr[i][j];
			}
		}
	}
	cout << number_dust;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> R >> C >> T;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cin >> arr[i][j];			
			if (arr[i][j] > 0) {
				dust.push(make_pair(i, j));
			}
			if (arr[i][j] == -1) {
				air_clean.push_back(make_pair(i, j));
			}
		}
	}
	solve();
	return 0;
}

 

질문 및 조언 댓글 남겨주세요