[백준] 미세먼지 안녕!

✔️ 문제

문제 링크 : https://www.acmicpc.net/problem/17144
삼성 SW 역량테스트 기출 문제다.

✔️ 문제 이해

집에는 공기청정기와 미세먼지들이 존재한다.
집은 R x C 격자판으로 나타낸다. 각 칸의 크기는 1 x 1 이다.
공기청정기는 항상 첫 번째 열에 설치돼 있고, 크기는 연속된 두 행을 차지한다. 공기청정기는 -1로 표현된다.
미세먼지는 격자판의 특정 위치 (r, c) 에 존재한다. 미세먼지는 정수로 표현된다. 정수는 미세먼지의 양을 나타낸다.
1초 동안 아래 적힌 일이 순서대로 일어난다. 아래 과정을 그대로 구현하면 된다.
- 모든 칸에서 동시에 미세먼지가 확산된다.
  - (r, c)에 있는 미세먼지는 인접한 4 방향으로 확산된다.
  - 인접한 방향에 공기청정기가 있거나, 칸이 없으면 확산은 일어나지 않는다.
  - 확산되는 양은 Ar,c / 5이고 소수점은 버린다.
  - (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
- 공기청정기가 작동한다.
  - 공기 청정기에서는 바람이 나온다.
  - 위쪽 공기청정기의 바람은 반시계 방향, 아래쪽 공기청정기의 바람은 시계 방향으로 순환한다.
  - 바람이 불면 미세먼지가 바람이 부는 방향으로 모두 한 칸씩 이동한다.
  - 공기청정기로 들어간 미세먼지는 모두 정화된다.
집의 정보가 2차원 배열로 주어졌을 때, T초가 지난후 남아있는 미세먼지의 양을 구해야 한다.
입력
- 첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.
- 둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

✔️ 알고리즘 설계

미세먼지를 확산 시킨다.
공기를 순환 시킨다.
1,2 를 T번 반복한 뒤 집에 남아있는 미세먼지의 총합을 출력한다.

✔️ 상세 구현설명

미세먼지 확산 : 문제 조건대로 집에 존재하는 모든 미세먼지에 대해 각 위치를 기준으로 4방향으로 확산 시킨다. 미세먼지의 양이 5 이상일 때만 확산이 진행된다. 모든 미세먼지는 동시에 확산 돼야한다. 주어진 2차원 배열만 이용해서 확산을 진행하면 먼저 확산 시킨 결과가 다른 결과에 영향을 줄 수 있다. 따라서 2 차원 배열 2개를 사용해서 하나는 확산을 위한 정보를 읽는 용도, 다른 하나는 확산의 결과를 저장시키는 용도로 사용한다. (주석 참고.)
공기 순환 : 문제에서 주어진 그림을 보면 공기 순환이 어떤식으로 이루어지는지 직관적으로 알 수 있다. 그림을 참고하여 바람의 방향대로 배열의 원소를 한 칸씩 옮겨주는 시뮬레이션을 구현하면 된다. 공기청정기로 들어간 미세먼지는 모두 정화된다. 따라서 공기청정기에서 바람이 나오는 위치는 항상 0으로 만들어 준다.

👨🏻‍💻 소스 코드

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int x, y;
int r, c, t;
int map[50][50];
int airConUpXpos;
const int dx[] = { 1,-1,0,0 }, dy[] = { 0,0,-1,1 };

void diffuseDust() {

	int tmpMap[50][50];

	// 동시 확산 처리를 위해, 원본 map을 임시 tmpMap에 복사해둔다. 
	memcpy(tmpMap, map, sizeof(map)); 

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (map[i][j] >= 5) { // 확산이 가능한 미세먼지인 경우.
				int diffuseAmount = map[i][j] / 5; // 확산될 미세먼지 양 계산.
				for (int k = 0; k < 4; k++) { // 상하좌우 인접 위치를 확인한다.
					int nx = i + dx[k], ny = j + dy[k];

					// 인접 위치에 공기 청정기가 있는 경우.
					if (map[nx][ny] == -1) continue; 

					// 범위를 벗어난 경우.
					if (nx >= r || nx < 0 || ny >= c || ny < 0) continue; 

					// map을 기준으로 확산여부를 판단하고, 결과반영은 tmpMap에 한다.
					// 이렇게 하면, map은 바뀌지 않으므로 먼저 확산시킨 먼지의 결과가 
					// 나중에 확산시킬 먼지의 결과에 영향을 주지 않게할 수 있다.

					// 인접 위치에 미세먼지 확산.
					tmpMap[nx][ny] += diffuseAmount; 

					// 확산 시켰으니까, 현재 위치 미세먼지 감소.
					tmpMap[i][j] -= diffuseAmount;  
				}
			}
		}
	}

	// map을 tmpMap으로 교체하여 원본 배열에 시뮬레이션 결과 반영.
	memcpy(map, tmpMap, sizeof(tmpMap)); 
}

void airConditionerWork() {

	// main에서 구한 에어컨 위쪽 좌표 기준으로 에어컨 위쪽 공기 순환 수행.
	x = airConUpXpos - 1, y = 0;
	while (x > 0) map[x][y] = map[x - 1][y], x--; // ↓

	x = 0, y = 0;
	while (y < c - 1) map[x][y] = map[x][y + 1], y++; // ←

	x = 0, y = c - 1;
	while (x < airConUpXpos)  map[x][y] = map[x + 1][y], x++; // ↑

	x = airConUpXpos, y = c - 1;
	while (y > 1) map[x][y] = map[x][y - 1], y--;  // →

	map[airConUpXpos][1] = 0; // 공기 청정기에서 공기가 나오는 부분은 0으로 만듦.

	// main에서 구한 에어컨 위쪽 좌표 + 1 = 에어컨 아래쪽 좌표
	// 에어컨 아래쪽 공기 순환 수행.

	int airConDownXpos = airConUpXpos + 1;

	x = airConDownXpos + 1, y = 0; // ↑
	while (x < r - 1) map[x][y] = map[x + 1][y], x++;

	x = r - 1, y = 0;
	while (y < c - 1) map[x][y] = map[x][y + 1], y++; // ←

	x = r - 1, y = c - 1;
	while (x > airConDownXpos) map[x][y] = map[x - 1][y], x--; // ↓

	x = airConDownXpos, y = c - 1;
	while (y > 1) map[x][y] = map[x][y - 1], y--; // →

	map[airConDownXpos][1] = 0; // 공기 청정기에서 공기가 나오는 부분은 0으로 만듦.

}

void solve() {

	while (t--) { // t초 만큼 시뮬레이션한다.
		diffuseDust(); // 먼지를 확산시킨다.
		airConditionerWork(); // 공기순환을 시킨다. 
	}

	int ret = 0;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (map[i][j] > 0) ret += map[i][j]; // 남아있는 미세먼지를 모두 더한다.
		}
	}

	cout << ret; // 결과 출력.
}

int main() {
	cin >> r >> c >> t; // 값 입력.
	bool flag = true;

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> map[i][j];
			if (map[i][j] == -1 && flag) {
				airConUpXpos = i;  // 에어컨 위쪽부분 X 좌표를 저장해둔다. 
				flag = false;
				// X 좌표만 저장해둬도 된다. 에어컨은 항상 왼쪽 첫째 열에 위치하기 때문.
				// 최초로 만나는 -1이 에어컨 위쪽 부분 X좌표이다.
				// flag를 통해 최초 한 번만 저장 하도록 구현.
			}
		}
	}

	solve();
	return 0;
}

✔️ 복기해야 할 지식

동시에 어떤 사건을 처리하는 시뮬레이션을 구현 할 때, 먼저 수행한 결과가 나중에 수행한 결과에 영향을 주지 않게 구현 해야한다.
<cstring> 헤더의 memcpy 함수를 사용하면 배열 복사를 쉽게 할 수 있다.

✔️ 문제 회고

주어진 문제를 그대로 구현하는 시뮬레이션 문제였다. 문제를 이해하는 능력, 능숙한 배열 조작 능력이 필요하다.
미세먼지 양이 5 이상일 경우에만 확산되는 것을 간과했었다.
모든 미세먼지가 동시에 확산 되도록 구현하는 부분을 간과했었다.
공기 순환 구현은 처음에 어렵게 느껴졌지만, 그냥 배열의 원소를 한 칸씩 옆으로 옮기면 됐다.
설계 및 구현 능력을 더 키워서 빠르게 푸는 능력을 길러야겠다.

Byung Wook Park (박병욱)

✔️ 문제

✔️ 문제 이해

✔️ 알고리즘 설계

✔️ 상세 구현설명

👨🏻‍💻 소스 코드

✔️ 복기해야 할 지식

✔️ 문제 회고