[백준 C++] 17144번 : 미세먼지 안녕!

1. 문제

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

17144번: 미세먼지 안녕!

 

2. 알고리즘 분류

• 구현
• 시뮬레이션

 

3. 소스 코드

 

 

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

int R, C, T;
int total_dust = 0;
int dr[] = { -1, 0, 1, 0 };	// row 방향배열
int dc[] = { 0, 1, 0, -1 };	// col 방향배열
int map[50][50];	// 맵 정보
vector<pair<int, int>> air_cleaner;	// 공기 청정기 위치

// 확산을 구현한 함수
void diffusion() {
	// 임시 맵 초기화
	int temp_map[50][50];
	for (int r = 0; r < R; r++)
		for (int c = 0; c < C; c++)
			temp_map[r][c] = 0;

	// 모든 맵 좌표 탐색
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (map[r][c] == 0) continue;	// 빈 칸이면 스킵

			if (map[r][c] == -1) {	// 공기청정기 위치면 스킵
				temp_map[r][c] = -1;
				continue;
			}

			temp_map[r][c] += map[r][c];	// 현재 미세먼지 값 저장
			int diffusion_quantity = map[r][c] / 5;	// 확산될 때 퍼져나가는 미세먼지량

			// 상하좌우 4방향 탐색
			for (int i = 0; i < 4; i++) {
				int next_r = r + dr[i];
				int next_c = c + dc[i];

				if (next_r < 0 || next_r >= R || next_c < 0 || next_c >= C) continue;	// 맵을 벗어나는 경우 스킵
				if (map[next_r][next_c] == -1) continue;	// 공기청정기 위치라면 스킵

				temp_map[next_r][next_c] += diffusion_quantity;	// 미세먼지 확산
				temp_map[r][c] -= diffusion_quantity;	// 확산량만큼 발생지에서 빼주기
			}
		}
	}

	// 임시 맵을 현재 맵에 복사
	for (int r = 0; r < R; r++)
		for (int c = 0; c < C; c++)
			map[r][c] = temp_map[r][c];
}

// 공기순환을 구현한 함수
void circulation() {

	// 미세먼지 흡입
	total_dust -= map[air_cleaner[0].first - 1][air_cleaner[0].second];
	total_dust -= map[air_cleaner[1].first + 1][air_cleaner[1].second];

	// 공기청정기 윗 공간
	// 아랫 방향
	for (int r = air_cleaner[0].first - 1; r > 0; r--)
		map[r][air_cleaner[0].second] = map[r - 1][air_cleaner[0].second];

	// 왼쪽 방향
	for (int c = air_cleaner[0].second; c < C - 1; c++)
		map[0][c] = map[0][c + 1];

	// 윗 방향
	for (int r = 0; r <= air_cleaner[0].first; r++)
		map[r][C - 1] = map[r + 1][C - 1];

	// 오른쪽 방향
	for (int c = C - 1; c > air_cleaner[0].second + 1; c--)
		map[air_cleaner[0].first][c] = map[air_cleaner[0].first][c - 1];

	map[air_cleaner[0].first][air_cleaner[0].second + 1] = 0;

	// 공기청정기 아랫 공간
	// 윗 방향
	for (int r = air_cleaner[1].first + 1; r < R - 1; r++)
		map[r][air_cleaner[1].second] = map[r + 1][air_cleaner[1].second];

	// 왼쪽 방향
	for (int c = air_cleaner[1].second; c < C - 1; c++)
		map[R - 1][c] = map[R - 1][c + 1];

	// 아랫 방향
	for (int r = R - 1; r > air_cleaner[1].first; r--)
		map[r][C - 1] = map[r - 1][C - 1];

	// 오른쪽 방향
	for (int c = C - 1; c > air_cleaner[1].second + 1; c--)
		map[air_cleaner[1].first][c] = map[air_cleaner[1].first][c - 1];

	map[air_cleaner[1].first][air_cleaner[1].second + 1] = 0;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// 입력
	cin >> R >> C >> T;

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> map[r][c];

			if (map[r][c] == -1) air_cleaner.push_back({ r, c });	// 공기청정기 위치 저장
			else total_dust += map[r][c];	// 총 먼지량 계산
		}
	}

	// 문제 해결
	// 시뮬레이션 돌릴 시간만큼 반복
	while (T--) {
		diffusion();
		circulation();
	}

	// 출력
	cout << total_dust;

	return 0;
}

 

4.  유용한 문법 및 알고리즘

4-1) 방향 배열을 통한 상하좌우 탐색

// 모든 맵 좌표 탐색
for (int r = 0; r < R; r++) {
	for (int c = 0; c < C; c++) {
		if (map[r][c] == 0) continue;	// 빈 칸이면 스킵

		if (map[r][c] == -1) {	// 공기청정기 위치면 스킵
			temp_map[r][c] = -1;
			continue;
		}

		temp_map[r][c] += map[r][c];	// 현재 미세먼지 값 저장
		int diffusion_quantity = map[r][c] / 5;	// 확산될 때 퍼져나가는 미세먼지량

		// 상하좌우 4방향 탐색
		for (int i = 0; i < 4; i++) {
			int next_r = r + dr[i];
			int next_c = c + dc[i];

			if (next_r < 0 || next_r >= R || next_c < 0 || next_c >= C) continue;	// 맵을 벗어나는 경우 스킵
			if (map[next_r][next_c] == -1) continue;	// 공기청정기 위치라면 스킵

			temp_map[next_r][next_c] += diffusion_quantity;	// 미세먼지 확산
			temp_map[r][c] -= diffusion_quantity;	// 확산량만큼 발생지에서 빼주기
		}
	}
}