백준 17144 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

 

- 단순 구현 문제이다. 이런 문제는 무조건 맞춰야 코딩테스트 합격이 가능하다고 생각. 푸는데 50분정도가 걸렸다.

 

- 삼성 기출문제들은 시간복잡도를 계산하는게 무의미한 것 같다. 굳이 계산하면 모든 좌표에 대해 rxc만큼의 spread 연산을 진행하고, 이 후  약 2r+2c만큼 추가 연산을 진행하고.. 이 과정들을 t번 반복하기 때문에 O(rct)이다.

 

- 가장 먼저 모든 좌표에 대해서 미세먼지 확산을 시키고, 그 결과를 temp_spread 배열에 저장한다. 그 후, 공기청정기를 작동시켜서 미세먼지들을 한 칸씩 이동시킨다. 이 과정을 t번 반복한 후, 모든 미세먼지의 합을 구하면 된다.

 

- 이 문제의 핵심은 미세먼지의 이동 부분이라고 생각한다. 이 부분은 for문을 활용해서 사각형 테두리를 단방향으로 한 칸씩 잘 옮기는 것이 중요하다. 실제로 구현을 해보면, 굉장히 헷갈리는 것을 알 수 있다. 그래서 공식처럼 계속 보다보면 눈에 익어서 쉬워질 것이라는 생각이 든다. 필자의 경우 하나의 배열에서 값의 이동을 구현하지 않고, 동일한 배열을 하나 더 만들어서 그 배열에 한 칸 이동한 값들을 대입하는 식으로 구현을 했다.

 

 

 

#include <iostream>
#include <cstring>
using namespace std;
int r, c, t;
int arr[50][50];
int temp_spread[50][50];
int temp_cleaner[50][50];
int dx[] = { 0,0,1,-1 };
int dy[] = { -1,1,0,0 };

void run_cleaner(int air_cleaner_head) {

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			temp_cleaner[i][j] = temp_spread[i][j];
		}
	}
	// 공기청청기 윗부분 작동
	for (int i = 1; i < c-1; i++)
		temp_cleaner[air_cleaner_head][i + 1] = temp_spread[air_cleaner_head][i];
	for (int i = air_cleaner_head; i > 0; i--)
		temp_cleaner[i - 1][c - 1] = temp_spread[i][c - 1];
	for (int i = c - 1; i > 0; i--)
		temp_cleaner[0][i - 1] = temp_spread[0][i];
	for (int i = 0; i < air_cleaner_head-1; i++)
		temp_cleaner[i + 1][0] = temp_spread[i][0];
	temp_cleaner[air_cleaner_head][1] = 0;
	// 공기청청기 아랫부분 작동
	for (int i = 1; i < c - 1; i++)
		temp_cleaner[air_cleaner_head+1][i + 1] = temp_spread[air_cleaner_head+1][i];
	for (int i = air_cleaner_head+1; i < r-1; i++)
		temp_cleaner[i + 1][c - 1] = temp_spread[i][c - 1];
	for (int i = c - 1; i > 0; i--)
		temp_cleaner[r-1][i - 1] = temp_spread[r-1][i];
	for (int i = r-1; i > air_cleaner_head+1; i--)
		temp_cleaner[i -1][0] = temp_spread[i][0];
	temp_cleaner[air_cleaner_head+1][1] = 0;
}
void spread(int x, int y) {
	int spread_num = 0;
	int spread_volume = arr[x][y] / 5;
	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) continue;
		if (arr[nx][ny] == -1) continue; // 공기청정기
		spread_num++;
		temp_spread[nx][ny] += spread_volume;
	}
	temp_spread[x][y] += arr[x][y] - (spread_num * spread_volume);
}
int main() {
	int air_cleaner_head = 0;
	cin >> r >> c >> t;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> arr[i][j];
			if (!air_cleaner_head && arr[i][j] == -1) air_cleaner_head = i;
		}
	}
	while (t--) {
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if(arr[i][j] && arr[i][j] != -1) spread(i, j);
			}
		}
		run_cleaner(air_cleaner_head);
		// 공기청정기 가동 이후 상태에 공기청정기 좌표값 추가
		temp_cleaner[air_cleaner_head][0] = -1;
		temp_cleaner[air_cleaner_head + 1][0] = -1;
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				arr[i][j] = temp_cleaner[i][j];
			}
		}
		memset(temp_spread, 0, sizeof(temp_spread));
		memset(temp_spread, 0, sizeof(temp_cleaner));
	}
	int answer = 0;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (arr[i][j] && arr[i][j] != -1) answer += arr[i][j];
		}
	}
	cout << answer;
	return 0;
}