[17144번 미세먼지 안녕!] - C++

[17144번 미세먼지 안녕!]
https://www.acmicpc.net/problem/17144

골드4 난이도에 맞지 않게 간단한 문제였다. 특별한 알고리즘도 필요하지 않았고, 구현 난이도도 높지 않았다.

풀이

크게 두 가지로 나눠서 구현했다. 미세먼지의 확산과 공기청정기 작동으로 나눴다.

1.

미세먼지의 확산

조금 주의해야할 부분은 주변의 미세먼지가 확산하면서 아직 확산을 시작하지 않은 인접한 미세먼지의 양에 영향을 준다는 점이다. 이 부분을 해결하기 위해 확산 시작 전에 공기청정기의 위치만 -1로 표시되어있는 임시 2차원 배열을 하나 만들어 주었다.

2중 for문으로 원본 2차원 배열을 순회하며 각 칸의 미세먼지를 확산시키면서 임시 2차원 배열의 알맞은 칸에 확산된 먼지의 양과 확산을 끝내고 남은 먼지의 양을 더해주었다.

2.

공기청정기의 작동

공기청정기의 작동도 두 가지 방향으로 나누어 구현했다.
counterClockFlow()와 clockFlow() 두 가지로 나누어 구현했다.

beforeDust에 옮기려고 하는 칸의 미세먼지의 양을 담았고, afterDust에 옮긴 이후의 칸의 미세먼지의 양을 담았다. while문 4번으로 네 방향을 모두 구현했다.

둘 중 한 가지 방향을 구현 완료했다면, 남은 방향은 row, col의 증감만 바꿔주면 반대 방향 구현이 완료된다.

C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
#define ll long long
#define INF 1e9
using namespace std;

int ans;
int dr[] = {-1,0,1,0};
int dc[] = {0,1,0,-1};
int room[51][51];
int r,c,T;
vector<pair<int,int> > airCleaner;

void disperse() {

	int tempRoom[51][51];
	memset(tempRoom,0,sizeof(tempRoom));
	for(int i=0;i<airCleaner.size();++i) {
		pair<int,int> p = airCleaner[i];
		tempRoom[p.first][p.second] = -1;
	}

	for(int i=1;i<=r;++i) {
		for(int j=1;j<=c;++j) {
			int cnt = 0;
			int dust = room[i][j] / 5;
			if(room[i][j] > 0) {
				for(int d=0;d<4;++d) {
					int ni,nj;
					ni = i+dr[d];
					nj = j+dc[d];

					if(1<=ni && ni<=r && 1<=nj && nj<=c && (room[ni][nj] != -1)) {
						tempRoom[ni][nj] += dust;
						cnt++;
					}
				}

				tempRoom[i][j] += room[i][j] - (dust*cnt);
			}
		}
	}

	for(int i=1;i<=r;++i) {
		for(int j=1;j<=c;++j) {
			room[i][j] = tempRoom[i][j];
		}
	}

	return;
}

void counterClockFlow() {

	int row,col;

	row = airCleaner[0].first;
	col = airCleaner[0].second + 1;
	int beforeDust=0,afterDust=0;

	beforeDust = room[row][col];
	room[row][col] = 0;

	while(col+1 <= c) {
		afterDust = room[row][col+1];
		room[row][col+1] = beforeDust;
		beforeDust = afterDust;
		col++;
	}

	while(row-1 >= 1) {
		afterDust = room[row-1][col];
		room[row-1][col] = beforeDust;
		beforeDust = afterDust;
		row--;
	}

	while(col-1 >= 1) {
		afterDust = room[row][col-1];
		room[row][col-1] = beforeDust;
		beforeDust = afterDust;
		col--;
	}

	while(row+1 <= airCleaner[0].first) {
		afterDust = room[row+1][col];
		if(afterDust == -1) {
			break;
		}

		room[row+1][col] = beforeDust;
		beforeDust = afterDust;
		row++;
	}

	return;
}

void clockFlow() {

	int row,col;

	row = airCleaner[1].first;
	col = airCleaner[1].second + 1;
	int beforeDust=0,afterDust=0;

	beforeDust = room[row][col];
	room[row][col] = 0;

	while(col+1 <= c) {
		afterDust = room[row][col+1];
		room[row][col+1] = beforeDust;
		beforeDust = afterDust;
		col++;
	}

	while(row+1 <= r) {
		afterDust = room[row+1][col];
		room[row+1][col] = beforeDust;
		beforeDust = afterDust;
		row++;
	}

	while(col-1 >= 1) {
		afterDust = room[row][col-1];
		room[row][col-1] = beforeDust;
		beforeDust = afterDust;
		col--;
	}

	while(row-1 >= airCleaner[1].first) {
		afterDust = room[row-1][col];
		if(afterDust == -1) {
			break;
		}

		room[row-1][col] = beforeDust;
		beforeDust = afterDust;
		row--;	
	}

	return;
}

void cleanAir() {

	counterClockFlow();
	clockFlow();

	return;
}

void sol() {
	
	disperse();
	cleanAir();

	return;
}

int main(void) {
	// ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

	scanf("%d%d%d", &r,&c,&T);
	for(int i=1;i<=r;++i) {
		for(int j=1;j<=c;++j) {
			scanf("%d", &room[i][j]);
			if(room[i][j] == -1) {
				airCleaner.push_back(make_pair(i,j));
			}
		}
	}

	while(T--) {
		sol();
	}

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

	printf("%d\n", ans);
	
	return 0;
}

실행 결과