삼성 코딩테스트 기출_(백준)미세먼지 안녕!

난이도 ★☆☆

 

문제출처

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

17144번: 미세먼지 안녕!

포인트

1. 확장 함수와 정화 함수 만들기

전체적인 구조 : 확장, 정화 함수를 따로 구현해 놓은 후, main에서 T의 횟수만큼 확장과 정화를 호출하는 형태로 구현한다.

 

2. (확장 함수 구현 시) 배열의 범위 및 공기청정기 자리 유의하기

공기청정기가 있는 자리와 배열의 바운더리를 넘어가는 범위에는 미세먼지 확장이 이루어지지 않음에 유의한다.

 

3. (정화 함수 구현 시) 정화되는 방향에 맞추어, 공기청정기에 빨려 들어가는 칸부터 한 칸씩 당기는 방식으로 구현하기

공기청정기에 빨려 들어가는 칸부터 화살표 반대 방향으로 움직이며 한 칸씩 당겨주면 깔끔한 구현이 가능하다.

 

정답코드

#include <iostream>
#include <vector>
using namespace std;

int R, C, T;
int a[51][51];
int amount[51][51];
vector<int> airFresher;

int dx[4] = { 0,0,1,-1 };
int dy[4] = { -1,1,0,0 };

//확장 함수
void spread() {
	//각 칸마다, 얼만큼의 미세먼지가 확장될지 미리 계산하여 amount 배열에 저장해 둠
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (a[i][j] != -1) {
				amount[i][j] = a[i][j] / 5;
			}
		}
	}
	
    //실제 확장이 일어나는 부분
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (a[i][j] != -1) {
				int dir = 0;
				for (int k = 0; k < 4; k++) {
					int nx = i + dx[k];
					int ny = j + dy[k];
					if (a[nx][ny] != -1 && nx >= 0 && ny >= 0 && nx < R && ny < C) {
						dir++;
						a[nx][ny] += amount[i][j];
					}
				}
				a[i][j] -= (amount[i][j] * dir);
			}
		}
	}
}

//정화 함수
void fresh() {
	//윗 부분 정화
	for (int i = airFresher[0]; i > 0; i--) {
		a[i][0] = a[i - 1][0];
	}
	a[airFresher[0]][0] = 0;
	for (int i = 0; i < C - 1; i++) {
		a[0][i] = a[0][i + 1];
	}
	for (int i = 0; i < airFresher[0]; i++) {
		a[i][C - 1] = a[i + 1][C - 1];
	}
	for (int i = C - 1; i > 0; i--) {
		a[airFresher[0]][i] = a[airFresher[0]][i - 1];
	}

	//아래 부분 정화
	for (int i = airFresher[1]; i < R - 1; i++) {
		a[i][0] = a[i + 1][0];
	}
	a[airFresher[1]][0] = 0;
	for (int i = 0; i < C - 1; i++) {
		a[R - 1][i] = a[R - 1][i + 1];
	}
	for (int i = R - 1; i > airFresher[1]; i--) {
		a[i][C - 1] = a[i - 1][C - 1];
	}
	for (int i = C - 1; i > 0; i--) {
		a[airFresher[1]][i] = a[airFresher[1]][i - 1];
	}
	
}

int main() {
	cin >> R >> C >> T;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> a[i][j];
			if (a[i][j] == -1) {
				airFresher.push_back(i);
			}
		}
	}

	//T횟수만큼 확장과 정화 호출
	while (T--) {
		spread();
		fresh();
	}

	//남은 미세먼지 양 카운트
	int ans = 0;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			ans += a[i][j];
		}
	}
	cout << ans << '\n';
	return 0;
}