백준 - 17144번: 미세먼지 안녕! 문제 풀이 과정 정리 (C++)

💎 "미세먼지 안녕!" 문제 풀이 정리!

이번에 카카오 코테를 보고 빡구현 문제를 조금 풀어봐야겠다 싶어서 이 문제를 풀게 되었습니다.

 

solved.ac에서 class 4에 있는 문제인데, 예전에 한 번 풀려다가 귀찮아서 안 풀었던 것도 생각나서 이번 기회에 정리해보려 합니다.

문제 링크😀

---

문제 설명

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
   • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
   • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
   • 확산되는 양은 Ar,c/5이고 소수점은 버린다.
   • (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
2. 공기청정기가 작동한다.
   • 공기청정기에서는 바람이 나온다.
   • 위쪽 공기청정기의 바람은 반시계 방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
   • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
   • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

다음은 확산의 예시이다.

왼쪽과 오른쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.

인접한 네 방향으로 모두 확산이 일어난다.

공기청정기가 있는 칸으로는 확산이 일어나지 않는다.

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

---

입력

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000)가 주어진다.

둘째 줄부터 R개의 줄에 Ar, c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar, c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸 이상 떨어져 있다.

---

출력

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

---

🔑 풀이 설명

사실 효율적으로 짜려고 하기보다는 귀찮아서 후딱 풀어보자는 느낌으로 풀었기 때문에, 개선할 만한 부분이 있을 것 같지만 귀찮기 때문에 다음에 유사한 문제를 풀이할 때 더 잘 짜 보려고 합니다.

 

어쨌든 이번 문제 설명을 이어가자면, 이번 문제는 빡구현 유형의 문제로 문제에서 요구하는 긴 요구사항을 따라서 그대로만 구현하니 맞출 수 있었습니다. (조금 오래 걸리긴 했습니다..)

 

저는 크게 다음과 같이 나눠서 구현해야겠다고 생각했습니다.

• 초기화 부분 (input)
• 미세먼지의 확산 (spreadDust)
• 공기청정기의 가동 (airfresherOn)
• 다양한 부가적 기능을 위해 구현해야 하는 함수들 (inRange, printStatus, totalDustAmount)

위 목록에서 중요하면서, 어려운 부분이 크게 두 가지인 것 같습니다. 먼저 미세먼지의 확산 다음으로는 당연하게 공기청정기의 가동 부분이죠

 

미세먼지는 동시에 확산이 되어야 하기 때문에, 단순하게 전체 집 배열의 칸을 돌면서 미세먼지가 있으니 바로 확산시키자!라고 구현할 수 없습니다. (이렇게 되면 미세먼지 확산으로 새로 미세먼지가 있는 칸이 생성되고 그에 따라서 계속 확산이 무한히 이어지기 때문이죠)

 

그래서 저는 확산 이전에 현재 상태에서 미세먼지가 있는 칸을 먼저 queue 자료 구조에 넣은 후에 queue에서 하나씩 빼면서 확산 과정을 처리하는 방식으로 구현했습니다. (이 queue에는 확산되는 미세먼지의 양도 같이 넣어줘야 합니다. 이는 확산 과정에서 미세먼지의 양이 달라지기 때문입니다! 😊)

 

이런 방식으로 미세먼지 확산 부분을 구현하고, 공기 청정기 기능 구현 부분은 그냥 시키는 대로 구현하니 상대적으로 간단하게(?) 구현할 수 있었습니다.

 

 

---

🏆 제출 코드 전체

/*
	Date: 2022/08/23
	Brief:

	Reference:
*/
#include <iostream>
#include <queue>

#define MAX 51

using namespace std;

int arr[MAX][MAX];
int r, c, t;

void input() {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> arr[i][j];
		}
	}
}

// (x, y)가 맵 내부인지 확인하는 함수이다.
bool inRange(int x, int y) {
	return (0 <= x && x < r && 0 <= y && y < c);
}

void spreadDust() {
	int dx[] = { -1, 1, 0, 0 };
	int dy[] = { 0, 0, -1, 1 };

	queue<pair<int, pair<int, int>>> q;

	// 먼저 현재 시점 기준으로 모든 미세 먼지의 위치와 퍼질 양을 큐에 담는다.
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			// 공기청정기는 건너 띈다.
			if (arr[i][j] == -1)
				continue;

			if (arr[i][j] != 0) {
				// 퍼질 미세먼지의 양과 위치를 큐에 담는다.
				q.push({ arr[i][j] / 5, {i, j} });
			}
		}
	}

	// queue에 담긴 미세먼지를 가능한 방향으로 한 번에 퍼뜨린다.
	while (!q.empty()) {
		int x = q.front().second.first;
		int y = q.front().second.second;
		int spreadDustAmount = q.front().first;

		q.pop();
		//cout << x << " " << y << " " << spreadDustAmount << endl;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (!inRange(nx, ny) || arr[nx][ny] == -1)
				continue;

			// 퍼진 만큼 해당 칸은 미세먼지가 증하고 원래 칸에는 줄어든다.
			arr[nx][ny] += spreadDustAmount;
			arr[x][y] -= spreadDustAmount;
		}
	}
}

void airfresherOn() {
	int first = 0, second = 1;

	// 우, 상, 좌, 하 순으로 공기가 순환한다.
	int dx1[] = { 0, -1, 0, 1 };
	int dy1[] = { 1, 0, -1, 0 };

	// 공기 청정기의 위치를 찾는다.
	for (int i = 0; i < r; i++) {
		if (arr[i][0] == -1) {
			first = i, second = i + 1;
			break;
		}
	}

	int x = first, y = 0;
	int prev = 0;
	int idx = 0;

	// 공기 청정기로 돌아올때까지 훑는다.
	while (1) {
		int nx = x + dx1[idx], ny = y + dy1[idx];
		
		// 맵의 끝을 넘어가면 탐색 방향을 바꾼다.
		if (!inRange(nx, ny)) {
			idx++;
			continue;
		}

		// 다시 공기청정기에 도달하면 공기 순환을 멈춘다.
		if (nx == first && ny == 0)
			break;

		// 해당 칸의 공기를 이동시키고 칸의 위치도 이동한다.
		int cur = arr[nx][ny];
		arr[nx][ny] = prev;
		prev = cur;
		x = nx, y = ny;
	}

	// 우, 하, 좌, 상 순으로 공기가 순환한다.
	int dx2[] = { 0, 1, 0, -1 };
	int dy2[] = { 1, 0, -1, 0 };


	x = second, y = 0;
	prev = 0;
	idx = 0;

	// 공기 청정기로 돌아올때까지 훑는다.
	while (1) {
		int nx = x + dx2[idx], ny = y + dy2[idx];

		// 맵의 끝을 넘어가면 탐색 방향을 바꾼다.
		if (!inRange(nx, ny)) {
			idx++;
			continue;
		}

		// 다시 공기청정기에 도달하면 공기 순환을 멈춘다.
		if (nx == second && ny == 0)
			break;

		// 해당 칸의 공기를 이동시키고 칸의 위치도 이동한다.
		int cur = arr[nx][ny];
		arr[nx][ny] = prev;
		prev = cur;
		x = nx, y = ny;
	}

	return;
}

int totalDustAmount() {
	int res = 0;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (arr[i][j] == -1)
				continue;
			res += arr[i][j];
		}
	}
	return res;
}

void printStatus() {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << arr[i][j] << " ";
		}
		cout << "\n";
	}
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> r >> c >> t;

	input();
	
	while (t--) {
		spreadDust();
		airfresherOn();
	}

	//printStatus();

	cout << totalDustAmount();
	return 0;
}