백준 17144_미세먼지 안녕!

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

17144번: 미세먼지 안녕!

해당 문제 역시 시뮬레이션 문제였다.

공기청정기의 조건들과 그 외 문제들의 조건들 덕에 조금 헤매긴 했지만 하드코딩으로 문제를 해결하였다.

해결은 먼지 확산과 공기청정기 작동 두 가지 함수로 나눠서 접근하였다.

 

기본적으로 공기청정기는 위 방향과 아래 방향으로 주어진다는 사실과 차례대로 하드코딩하니 문제는 풀 수 있었지만 다소 아쉬움이 남는 풀이여서 다른 사람들의 풀이를 조금 찾아봤더니 공기청정기의 과정을 축소할 수 있을 것 같다.

방향에 따라 하나씩 나누는 방식이 아닌 예외 케이스만 잘 고려한다면 하나의 반복문으로 충분히 처리가능 할 듯하다.

다만 실제 시험에서는 바로 바로 생각이 날 수 있을지 모르겠다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n, m, t;
int mp[50][50];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
// 위치, 방향(even idx = 반시계, odd idx = 시계)
vector<pair<int,int>> cl; 

// 확산
void scatter() {
	// copy
	int mpc[50][50];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			mpc[i][j] = 0; // 1 초 후 변해야할 값
	
	// 확산
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			// 값이 있으면
			if (mp[i][j] > 0) {
				int dcnt = 0, x, y;
				int val = mp[i][j] / 5;

				// 4방 변화 값(0~3)
				for (int k = 0; k < 4; k++) {
					x = i + dx[k], y = j + dy[k];
					if (x >= 0 && x < n && y >= 0 && y < m && mp[x][y] != -1) {
						mpc[x][y] += val; // 더하기
						dcnt++;
					}
				}
				// 빼진 값 빼기
				mpc[i][j] -= (val * dcnt);
			}
		}
	}

	// 확산변화값 처리
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			// 청정기는 넘어간다
			if (mp[i][j] == -1)
				continue;
			mp[i][j] += mpc[i][j]; // 변화 값 처리
		}
	}
	
}

// 청정
void clean() {
	// 청정기 개수 동장
	for (int idx = 0; idx < cl.size(); idx++) {
		int c = 1; // 회전방향
		if (idx % 2 == 0)
			c *= -1;
		// 청정기 위치
		int x = cl[idx].first, y = cl[idx].second;

		// 시계 방향
		if (c == 1) {
			// 2 1 0 3
			int d = 3;
			int nx = x, ny = y;
			for (int k = 0; k < 4; k++) {
				if (d == 0)
					d = 3;
				else
					d = (d - 1) % 4; // 시계
				// 남 2
				if (d == 2) {
					nx = x + dx[d], ny = y + dy[d]; // 탐색 위치
					while ( nx != n - 1) {
						int nx2  = nx + dx[d], ny2 = ny + dy[d]; // 다음 위치
						mp[nx][ny] = mp[nx2][ny2]; // 흡수
						nx = nx + dx[d], ny = ny + dy[d]; // 이동
					}
				}
				// 동 1
				else if (d == 1) {
					while (ny >= 0 && ny < m - 1) {
						int nx2 = nx + dx[d], ny2 = ny + dy[d]; // 다음 위치
						mp[nx][ny] = mp[nx2][ny2]; // 흡수
						nx = nx + dx[d], ny = ny + dy[d]; // 이동
					}
				}
				// 북 0
				else if(d == 0) {
					// 청소기 위치보다 위로가지 않게
					while (nx != x) {
						int nx2 = nx + dx[d], ny2 = ny + dy[d]; // 다음 위치
						mp[nx][ny] = mp[nx2][ny2]; // 흡수
						nx = nx + dx[d], ny = ny + dy[d]; // 이동
					}
				}
				
				// 서 3
				else if (d == 3) {
					while (ny!=1) {
						int nx2 = nx + dx[d], ny2 = ny + dy[d]; // 다음 위치
						mp[nx][ny] = mp[nx2][ny2]; // 흡수
						nx = nx + dx[d], ny = ny + dy[d]; // 이동
					}
					mp[nx][ny] = 0;
				}
			}
		}

		// 반시계 방향
		else if (c == -1) {
			// 0 1 2 3
			int d = 3;
			int nx = x, ny = y;
			for (int k = 0; k < 4; k++) {
				d = (d + 1) % 4; // 시계
				// 북 0
				if (d == 0) {
					nx = x + dx[d], ny = y + dy[d]; // 탐색 위치
					while (nx != 0) {
						int nx2 = nx + dx[d], ny2 = ny + dy[d]; // 다음 위치
						mp[nx][ny] = mp[nx2][ny2]; // 흡수
						nx = nx + dx[d], ny = ny + dy[d]; // 이동
					}
				}
				// 동 1
				else if (d == 1) {
					while (ny != m - 1) {
						int nx2 = nx + dx[d], ny2 = ny + dy[d]; // 다음 위치
						mp[nx][ny] = mp[nx2][ny2]; // 흡수
						nx = nx + dx[d], ny = ny + dy[d]; // 이동
					}
				}
				// 남 2
				else if (d == 2) {
					// 청소기 위치보다 위로가지 않게
					while (nx != x) {
						int nx2 = nx + dx[d], ny2 = ny + dy[d]; // 다음 위치
						mp[nx][ny] = mp[nx2][ny2]; // 흡수
						nx = nx + dx[d], ny = ny + dy[d]; // 이동
					}
				}

				// 서 3
				else if (d == 3) {
					while (ny != 1) {
						int nx2 = nx + dx[d], ny2 = ny + dy[d]; // 다음 위치
						mp[nx][ny] = mp[nx2][ny2]; // 흡수
						nx = nx + dx[d], ny = ny + dy[d]; // 이동
					}
					mp[nx][ny] = 0;
				}
			}
		}
	}
}

int main() {
	cin >> n >> m >> t;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> mp[i][j];
			if (mp[i][j] == -1) {
				pair<int, int> p(i, j);
				cl.push_back(p);
			}
		}
	}

	// t초후
	for (int i = 0; i < t; i++) {
		scatter();
		clean();
	}

	// 정답
	int ans = 0;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < m; j++)
			if (mp[i][j] > 0)
				ans += mp[i][j];

	cout << ans;
}