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

 

안녕하세요 (｡･∀･)ﾉ

오늘도 삼성 SW 역량 테스트 기출 문제를 풀어보았습니다!

 

백준 17144번

17144번: 미세먼지 안녕!

 

이번 문제는 시뮬레이션 문제입니다!

개인적으로 시뮬레이션 문제는 문제가 길고 그림이 많아서 굉장히 풀기 싫지만(?),

막상 풀어보면 아주 쉽게 해결할 수 있는 문제인 것 같습니다 :)

코딩 테스트 문제에는 시뮬레이션이 특히 많은 것 같네요 ㅎㅎ

 

저는 문제를 단계별로 나누어 구현해보았습니다.

우선 문제에 주어진 동작 순서를 확인해보도록 합시다.

문제에서 주어진 동작 순서

우리가 구현해야 할 부분은 크게 3가지입니다.

1. 미세먼지 확산시키기

2. 공기청정기 작동시키기

3. 남아있는 미세먼지의 양 구하기

 

1. 미세먼지 확산시키기

문제에서 주어진 조건을 보면 미세먼지가 있는 칸에서는 미세먼지가 인접한 네 방향으로 확산되는 것을 알 수 있습니다.

하지만 만약 인접한 방향에 공기청정기가 있거나, 칸이 존재하지 않으면 확산이 일어나지 않습니다.

공기청정기가 있는 칸이 -1이라고 주어졌기 때문에 저는 비교의 편의성을 위해 존재하지 않는 칸 역시 -1로 설정해주었습니다!

(초기에 Ar,c의 배열을 -1로 초기화하였습니다.)

그리고 해당 문제에서 미세먼지의 확산은 모든 칸에서 동시에 일어난다고 하였습니다.

만약 확산이 순차적으로 일어난다면 주어진 Ar,c 배열 내에서 계산을 진행하면 되지만,

확산이 동시에 일어나기 때문에 초기의 상태를 담고 있는 배열을 별도로 저장해주어야 합니다.

(코드 상으로는 실제 동시 탐색이 불가능하고, 앞에서부터 순차적으로 탐색해야 하기 때문에 원본 배열이 필요)

따라서 저는 Ar,c를 저장하는 구조체를 하나 만들어서 before(원본)와 after(현재)를 별도로 저장하였습니다.

마지막으로 인접한 방향으로 미세먼지를 확산시켜 줍니다.

이때 고려해야 할 점은 남은 미세먼지의 양을 계산해야 하기 때문에 확산된 방향의 개수를 count를 해주어야 합니다.

만약 현재 위치가 (r, c)라고 한다면 before(원본) 배열을 기준으로

- 상: (r-1, c)

- 하: (r+1, c)

- 좌: (r, c-1)

- 우: (r, c+1)

4가지 케이스가 각각 존재하는 칸인지 확인한 후, 존재한다면 해당 칸에 Ar,c(원본 배열)/5를 Ar,c(현재 배열) 값에 더해줍니다.

그리고 Ar,c(현재 배열)에는 남아있는 미세먼지의 양을 계산합니다.

before(원본)와 after(현재)를 적절하게 구분만 해준다면 1번 단계는 쉽게 구현할 수 있습니다!

2. 공기청정기 작동시키기

다음으로는 공기청정기를 작동시키는 과정입니다.

공기청정기 작동의 경우에는 위쪽 공기청정기와 아래쪽 공기청정기로 나누어 구현해주어야 합니다.

(위/아래에 따라 바람의 방향이 달라지기 때문)

공기청정기 바람의 순환

문제에서 주어진 그림 + 공기청정기가 1번 열에만 존재한다는 조건을 기준으로 규칙을 찾을 수 있습니다.

참고로 바람의 방향을 4단계(↓, →, ↑, ←)로 나누면 쉽게 생각할 수 있습니다.

● 위쪽 공기청정기

위쪽 공기청정기 순환

위쪽 공기청정기 바람의 방향과 각각의 좌표값을 살펴보면 다음과 같습니다.

참고로 up은 공기청정기 위쪽의 x 좌표값, C는 입력으로 받은 격자판 열을 의미합니다.

해당 좌표값을 바탕으로 1~4번 바람을 이동시켜주면 됩니다.

예를 들어 1번 바람은 위에서 아래로 흐르는 바람 방향으로, 주어진 값들을 아래로 한 칸씩 밀어주면 됩니다.

이때 주어진 값을 아래로 밀어주기 위해서는 아래에서부터 이동을 시작하여야 합니다. (값의 훼손을 방지하기 위해)

즉 (2, 1)을 (up-1, 1)로 (1, 1)을 (2, 1)로 이동시켜주면 되겠죠!

참고로 (up-1, 1)은 공기청정기로 들어간 값이기 때문에 (2, 1)로 덮어 쓰이도록 그냥 두면 됩니다!

마지막으로 주의해야 할 점은 (up, 2)는 새로운 공기가 나온 것이기 때문에 0으로 채워주어야 한다는 것입니다.

 

● 아래쪽 공기청정기

아래쪽 공기청정기 순환

아래쪽 공기청정기 역시 좌표값과 이동 방향만 달라졌을 뿐 좌표값을 기준으로 각각의 값들을 밀어주는 것은 동일합니다.

위의 사진을 참고하면 1~4번 바람의 이동을 쉽게 구할 수 있습니다.

마지막으로 아래쪽 공기청정기도 위쪽 공기청정기와 마찬가지로 새로운 바람이 나온 (down, 2) 공간에는 0을 채워주어야 합니다.

3. 남아있는 미세먼지의 양 구하기

남아있는 미세먼지의 양은 최종적으로 구한  Ar,c 배열에서 값이 0이거나 -1인 경우를 제외하고 모두 더해주면 됩니다.

(0인 경우: 미세먼지가 없음 / -1인 경우: 공기청정기의 위치)

 

이를 바탕으로 구현한 코드는 아래와 같습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX 51

int R, C, T;
int up, down; // 공기청정기의 위치 저장
typedef struct Area {
	int before; // 원본 배열 저장
	int after; // 현재 상태를 저장
}Area;
Area area[52][52];

void spread_check(int i, int j) {
	int cnt = 0;
	int spread_value = area[i][j].before / 5;
	// 상
	if (area[i - 1][j].before != -1) {
		area[i - 1][j].after += spread_value;
		cnt++;
	}
	// 하
	if (area[i + 1][j].before != -1) {
		area[i + 1][j].after += spread_value;
		cnt++;
	}
	// 좌
	if (area[i][j - 1].before != -1) {
		area[i][j - 1].after += spread_value;
		cnt++;
	}
	// 우
	if (area[i][j + 1].before != -1) {
		area[i][j + 1].after += spread_value;
		cnt++;
	}
	// 남아있는 미세먼지 양 계산
	area[i][j].after += area[i][j].before - spread_value * cnt;
}
void spread() {
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (area[i][j].before == 0 || area[i][j].before == -1)
				continue;
			spread_check(i, j);
		}
	}
}

void machine_up() {
	for (int i = up - 2; i >= 1; i--)
		area[i + 1][1].after = area[i][1].after;
	for (int i = 2; i <= C; i++)
		area[1][i - 1].after = area[1][i].after;
	for (int i = 2; i <= up; i++)
		area[i - 1][C].after = area[i][C].after;
	for (int i = C - 1; i >= 2; i--)
		area[up][i + 1].after = area[up][i].after;
	area[up][2].after = 0;
}
void machine_down() {
	for (int i = down + 2; i <= R; i++)
		area[i - 1][1].after = area[i][1].after;
	for (int i = 2; i <= C; i++)
		area[R][i - 1].after = area[R][i].after;
	for (int i = R - 1; i >= down; i--)
		area[i + 1][C].after = area[i][C].after;
	for (int i = C - 1; i >= 2; i--)
		area[down][i + 1].after = area[down][i].after;
	area[down][2].after = 0;
}
void machine() {
	machine_up();
	machine_down();
}

int dust_count() {
	int sum = 0;
	for (int i = 1; i <= R; i++)
		for (int j = 1; j <= C; j++)
			if (area[i][j].before != 0 && area[i][j].before != -1)
				sum += area[i][j].before;

	return sum;
}

void initialize() {
	for (int i = 1; i <= R; i++)
		for (int j = 1; j <= C; j++) {
			area[i][j].before = area[i][j].after;
			area[i][j].after = 0;
		}
	area[up][1].after = -1;
	area[down][1].after = -1;
}

int main() {

	scanf("%d%d%d", &R, &C, &T);
	for (int i = 0; i <= MAX; i++)
		for (int j = 0; j <= MAX; j++) {
			area[i][j].before = -1;
			area[i][j].after = 0;
		}
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			scanf("%d", &area[i][j].before);
			if (area[i][j].before == -1 && up == 0) {
				up = i;
				down = i + 1;
			}
		}
	}
	area[up][1].after = -1;
	area[down][1].after = -1;

	for (int i = 0; i < T; i++) {
		spread(); // 1번 과정
		machine(); // 2번 과정
		initialize(); // 다음 단계를 위해 현재 상태(after)를 원본 배열(before)로 저장
	}

	printf("%d\n", dust_count()); // 3번 과정

	return 0;
}

 

1. 미세먼지 확산시키기

spread() 함수를 통해 앞에서부터 미세먼지가 존재하는 칸을 탐색합니다.

이후 spread_check() 함수를 호출하여 해당 칸을 기준으로 상, 하, 좌, 우를 확인한 후 미세먼지를 확산시킵니다.

2. 공기청정기 작동시키기

machine() 함수를 호출하고 해당 함수에서는 machine_up() 함수와 machine_down() 함수를 호출함으로써

공기청정기의 위쪽과 아래쪽 바람을 순환시킵니다.

3. 남아있는 미세먼지의 양 구하기

마지막으로 dust_count() 함수를 통해 남아있는 미세먼지의 양을 구합니다.

 

이번 문제는 원본을 따로 저장해야 한다는 점만 고려하면 쉽게 구현할 수 있었습니다!

다음 주에는 또 새로운 문제를 풀어보도록 하겠습니다 ^0^