[백준 17144 / C++] 미세먼지 안녕!

살짝 노가다 문제이긴 한데 한번 풀어보면 괜찮은 문제이다. 

 

1. map 에서 미세먼지의 수치가 저장되어 있는 좌표값들을 모두 큐에 넣는다. 

2. 큐에 있는 좌표값들을 꺼집어 내서 상하좌우에 해당하는 규칙에 따라 값을 갱신한다. 

3. 갱신한 맵을 공기청정기를 중심으로 공기가 정화되게끔 map의 원소값을 시계 방향, 반시계 방향으로 이동시킨다.  

4. time이 입력한 값이 되면 맵의 모든 미세먼지 값을 더해서 출력해준다. 

#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
#include <algorithm>
using namespace std;
queue <pair <int, int>> q; 
int map[50][50]; 
int map_sum[50][50]; 
int m, n, time; 
int dy[4] = { 0,0,-1,1 }; 
int dx[4] = { 1,-1,0,0 };
vector <pair<int, int>> lo;
void bfs() {
	int t = 0; 
	int r1_y, r1_x, r2_y, r2_x;
	r1_y = lo[0].first; 
	r1_x = lo[0].second; 
	r2_y = lo[1].first; 
	r2_x = lo[1].second; 	
	while (!q.empty()) {
		if (t == time)return ; 
		int q_s = q.size(); 
		while (q_s--) {
			int y, x; 
			tie(y, x) = q.front(); 	 
			q.pop(); 
			int cnt = 0; 
			for (int i = 0; i < 4; i++) {
				int ny = dy[i] + y;
				int nx = dx[i] + x;
				if (ny < 0 || ny >= m || nx < 0 || nx >= n)continue;
				if (map[ny][nx] == -1)continue;
				cnt++;			
				map_sum[ny][nx] += (map[y][x] / 5);
			}
			if(cnt)	map_sum[y][x] += map[y][x] - ((map[y][x] / 5) * cnt); 
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j] == -1)map[i][j] = -1;
				else map[i][j] = map_sum[i][j];
				map_sum[i][j] = 0;
			}
		}	

		for (int i = lo[0].first - 1; i > 0; i--)map[i][0] = map[i - 1][0];	
		for (int i = 0; i < n - 1; i++)	map[0][i] = map[0][i + 1];	
		for (int i = 1; i <= lo[0].first; i++) map[i - 1][n - 1] = map[i][n - 1];
		for (int i = n - 1; i > 1; i--)map[lo[0].first][i] = map[lo[0].first][i - 1];
		map[lo[0].first][1] = 0;
		for (int i = lo[1].first + 1; i < m - 1; i++)map[i][0] = map[i + 1][0];
		for (int i = 0; i < n - 1; i++)	map[m - 1][i] = map[m - 1][i + 1];
		for (int i = m - 1; i >= lo[1].first; i--)map[i][n - 1] = map[i - 1][n - 1];
		for (int i = n - 1; i > 1; i--)	map[lo[1].first][i] = map[lo[1].first][i - 1];		
        map[lo[1].first][1] = 0;
		t++; 
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {	
				if (map[i][j] > 0)q.push({ i,j });
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false); 
	cin.tie(0); 
	cout.tie(0); 
	cin >> m >> n >> time; 	
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j]; 
			if (map[i][j] == -1) {
			   lo.push_back({ i,j }); 
			}
			else if (map[i][j] > 0) {
				q.push({ i,j }); 
			}
		}
	}	
	bfs(); 
	int result = 0; 
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {		
			if (map[i][j] == -1)continue; 
			result += map[i][j];
		}
	}
	cout << result; 
}

 

17144번: 미세먼지 안녕!