백준 17144번 미세먼지 안녕!

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

 

 

 

 

 

미세먼지가 확산되고 공기청정기가 작동하는 방법을 어렵지 않게 이해할 수 있었다.

 

해결 순서는 다음과 같다.

1. 미세먼지를 확산시킨다.

2. 공기청정기를 작동한다.

3. 위 과정을 t번 반복한다.

 

중요한 것은 초기에 미세먼지가 입력되는 위치와 값을 어떤 자료구조에 저장하고 있어야 한다.

 

만약 현재 위치에 미세먼지가 없었고, 옆방향에서 확산된 미세먼지로 인해 현재 위치에 미세먼지가 생길 수 있는데 이러한 경우는 현재 위치에서 미세먼지 양을 조절하지 않는다.

 

따라서 입력된 미세먼지의 좌표값과 미세먼지의 양을 큐에 따로 저장한 뒤  큐에서 하나씩 빼가면서 확산시켰다.

확산되는 방향은 상하좌우 4방향이므로 각 위치에서 4번씩만 확인하면 된다.

 

여기서 확산된 방향의 개수를 저장하기 위한 cnt변수를 0으로 초기화했어야 하는데 4로 초기화해버려서 로직에는 이상이 없는데 자꾸 결과가 이상하게 나와서 이거 찾느라 시간을 많이 잡아먹었다.

 

공기청정기는 위, 아래 2개로 나누어져 있기 때문에 차례대로 작동시켰다.

temp[][]에 미세먼지가 확산된 결과값을 저장하고 공기청정기가 작동하는 방향에 따라 map[][]의 값을 temp에서 하나씩 빼오면서 변경하였다.

 

미세먼지는 map의 경계 전까지만 밀 수 있으므로 map의 각 경계 전까지만 밀어버리고 그 뒤에는 방향을 바꿔서 다시 처리하면 된다.

 

 

#include <iostream>
#include <math.h>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

int map[50][50] = { 0 };
int temp[50][50] = { 0 };
int r, c, t;
int cx, cy; 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int ans = 0;


int cnt = 0;
queue<pair<int, int>> q; //미세먼지 좌표
queue<int> value; //미세먼지 값


int main() {

	cin >> r >> c >> t;


	
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> map[i][j];

			if (map[i][j] == -1) {//아래쪽 공기청정기 좌표값 저장
				cx = i;
				cy = j;

			}
			else if (map[i][j] != 0 && map[i][j] != -1) { //미세먼지의 위치
				q.push(make_pair(i, j));
				value.push(map[i][j]);
			}
		}
	}
		
	while (t--) {
		//미세먼지 확산
		while (!q.empty()) {
			int x = q.front().first;
			int y = q.front().second;
			int v = value.front();
			int munji = 0;
			munji = floor(v / 5);

			//4방향 위치 확인 후 미세먼지 퍼뜨리기
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];

				if (nx >= 0 && nx < r && ny >= 0 && ny < c && map[nx][ny] != -1) {
					cnt++;
					map[nx][ny] += munji;
				}
			}

			//4방향 퍼뜨린 후 자신의 미세먼지 값도 변화
			map[x][y] = map[x][y] - (munji*cnt);
			cnt = 0;

			q.pop();
			value.pop();
		}

		



		//미세먼지가 퍼진 상태를 복사
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				temp[i][j] = map[i][j];
			}
		}



		//아래쪽 공기청정기 작동
		int nx = cx;
		int ny = cy + 2;
		map[nx][ny - 1] = 0;

		//첫번째 방향으로 밀기(우)
		while (ny <= c - 1) {
			map[nx][ny] = temp[nx][ny - 1];
			ny++;			
		}

		//두번째 방향으로 밀기(하)
		nx = cx + 1;
		ny = c - 1;
		
		while (nx < r) {
			map[nx][ny] = temp[nx - 1][ny];
			nx++;
		}
		
		//세번째 방향으로 밀기(좌)
		nx = r - 1;
		ny = c - 2;
		
		while (ny >= 0) {
			map[nx][ny] = temp[nx][ny + 1];
			ny--;
		}
		
		//네번째 방향으로 밀기(상)
		nx = r - 2;
		ny = 0;
		
		while (map[nx][ny] != -1) {
			map[nx][ny] = temp[nx + 1][ny];
			nx--;
		}




		//윗쪽 공기청정기 작동
		nx = cx - 1;
		ny = cy + 2;
		map[nx][ny - 1] = 0;

		//첫번째 방향으로 밀기(우)
		while (ny <= c - 1) {
			map[nx][ny] = temp[nx][ny - 1];
			ny++;
		}

		//두번째 방향으로 밀기 (상)
		nx = cx - 2;
		ny = c - 1;
	
		while (nx >= 0) {
			map[nx][ny] = temp[nx + 1][ny];
			nx--;
		}
		

		//세번쨰 방향으로 밀기(좌)
		nx = 0;
		ny = c - 2;
	
		while (ny >= 0) {
			map[nx][ny] = temp[nx][ny + 1];
			ny--;
		}
		

		//네번째 방향으로 밀기(하)
		nx = 1;
		ny = 0;
		
		while (map[nx][ny] != -1) {
			map[nx][ny] = temp[nx - 1][ny];
			nx++;
		}
		


		//현재 map에 대한 미세먼지 위치와 값을 새로 저장
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (map[i][j] != 0 && map[i][j] != -1) {
					q.push(make_pair(i, j));
					value.push(map[i][j]);
				}
			}
		}
	}

	
	

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (map[i][j] > 0) {
				ans += map[i][j];
			}
		}
	}
	
	cout << ans;



	return 0;
}