BOJ 17144. 미세먼지 안녕!

24-02-10

🙇‍♀️[Gold IV] 미세먼지 안녕! - 17144

문제 링크

성능 요약

메모리: 2488 KB, 시간: 112 ms

분류

구현, 시뮬레이션

제출 일자

2024년 2월 10일 15:58:22

문제 설명

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

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

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

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

다음은 확산의 예시이다.

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

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

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

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

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

입력

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

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

출력

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

🚀풀이

로직

미세먼지가 확산된다.
공기청정기가 작동한다.

공청기 위아래를 알아야함.

확산은 모든 칸에서 동시에 일어남.
네 방향으로 확산.
네 방향 중 공청있거나 칸없으면 확산 X
확산의 양은 x/5, 소수점은 버림
남은 미세먼지양은 (x - x/5 * 확산된 방향 수)

함수들과 전역 변수 구조체는 아래와 같이 잡았다.

void setting();
void solve();
void spreadDustAll();
void spreadDust(int y, int x);
void OnAirPurification();
void UpAirPurification();
void UnderAirPurification();
void printBoard();

// 1. 미세먼지가 확산된다.
// 2. 공기청정기가 작동한다.
// 공청기 위아래를 알아야함.

struct SmallDust
{
	int y, x;
	int smallDust;
};

int R, C, T; // 행, 열, 시간
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
vector<vector<int>> board;
vector<pair<int, int>> dusts;
vector<SmallDust> smallDusts;
pair<int, int> upAirPurification, underAirPurification;

입력 값을 받으면서 공기 청정기(공청기) 의 위아래 위치를 기억해 줬다.

void setting()
{
	cin >> R >> C >> T;
	board = vector<vector<int>>(R + 1, vector<int>(C + 1));

	bool flag = false;
	for (int i = 1; i <= R; ++i)
	{
		for (int j = 1; j <= C; ++j)
		{
			cin >> board[i][j];
			if (board[i][j] != 0 && board[i][j] != -1)
				dusts.push_back({ i, j });
			if (board[i][j] == -1)
			{
				if (flag == false)
				{
					upAirPurification = { i, j };
					flag = true;
				}
				else
				{
					underAirPurification = { i , j };
				}
			}
		}
	}
}

먼지가 확산하는 것은 동시에 일어난다.

그러므로 현재 상태에서 먼저 확산을 다 시키고 작은 먼지들을 합산하는 것은 나중에 해야한다.

void spreadDustAll()
{
	// 확산은 모든 칸에서 동시에 일어남.
	// 네 방향으로 확산.
	// 네 방향 중 공청있거나 칸없으면 확산 X
	// 확산의 양은 x/5, 소수점은 버림
	// 남은 미세먼지양은 (x - x/5 * 확산된 방향 수)

	for (int i = 0; i < dusts.size(); ++i)
	{
		spreadDust(dusts[i].first, dusts[i].second);
	}

	// smallDust들을 더해주기
	dusts.clear();
	for (int i = 0; i < smallDusts.size(); ++i)
	{
		board[smallDusts[i].y][smallDusts[i].x] += smallDusts[i].smallDust;
	}

	smallDusts.clear();
}

먼지 확산의 함수는 아래와 같다.

void spreadDust(int y, int x)
{
	// 확산은 모든 칸에서 동시에 일어남.
	// 네 방향으로 확산.
	// 네 방향 중 공청있거나 칸없으면 확산 X
	// 확산의 양은 x/5, 소수점은 버림
	// 남은 미세먼지양은 (x - x/5 * 확산된 방향 수)

	if (y == 3 && x == 7)
	{
		int a = 1;
	}
	if (y == 5 && x == 7)
	{
		int a = 1;
	}

	int cnt = 0;
	int smallDust = board[y][x] / 5;
	for (int i = 0; i < 4; ++i)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 1 || nx < 1 || ny > R || nx > C)
			continue;
		if (board[ny][nx] == -1)
			continue;

		cnt++;

		// 다 퍼진 뒤 더해줘야함.
		smallDusts.push_back({ ny, nx, smallDust });
		//board[ny][nx] += smallDust; 바로 이렇게 더하면 안된다.
	}

	board[y][x] = board[y][x] - smallDust * cnt;
}

먼지가 다 퍼지면 공청기를 돌린다.

공청기를 다 돌리면 먼지들을 다시 기억해준다.

void OnAirPurification()
{
	UpAirPurification();
	UnderAirPurification();

	for (int i = 1; i <= R; ++i)
	{
		for (int j = 1; j <= C; ++j)
		{
			if (board[i][j] != 0 && board[i][j] != -1)
				dusts.push_back({ i, j });
		}
	}
}

공청기는 위아래로 나뉘어져있으므로 함수를 두 개 만들었다.

공청기 위쪽 함수

void UpAirPurification()
{
	// 반시계 방향으로 순환함.

	// upAirPurification위치까지
	for (int i = upAirPurification.first - 1; i > 1; --i)
	{
		board[i][1] = board[i - 1][1];
	}

	// 왼쪽 벽까지
	for (int i = 1; i < C; ++i)
	{
		board[1][i] = board[1][i + 1];
	}

	// 위쪽 벽까지
	for (int i = 1; i < upAirPurification.first; ++i)
	{
		board[i][C] = board[i + 1][C];
	}

	// 오른쪽 벽까지 가기
	for (int i = C; i > 2; --i)
	{
		board[upAirPurification.first][i] = board[upAirPurification.first][i - 1];
	}
	board[upAirPurification.first][2] = 0;

}

공청기 아래쪽 함수

void UnderAirPurification()
{
	// 시계 방향으로 순환함.

	// underAirPurification위치까지
	for (int i = underAirPurification.first + 1; i < R ; ++i)
	{
		board[i][1] = board[i + 1][1];
	}

	// 왼쪽 벽까지
	for (int i = 1; i < C; ++i)
	{
		board[R][i] = board[R][i + 1];
	}

	// 아래쪽 벽까지
	for (int i = R; i > underAirPurification.first; --i)
	{
		board[i][C] = board[i - 1][C];
	}

	// 오른쪽 벽까지 가기
	for (int i = C; i > 2; --i)
	{
		board[underAirPurification.first][i] = board[underAirPurification.first][i - 1];
	}
	board[underAirPurification.first][2] = 0;

}

최종적인 solve함수는 아래와 같다.

void solve()
{
	setting();

	for (int i = 0; i < T; ++i)
	{
		spreadDustAll();

		OnAirPurification();
	}

	int res = 0;

	for (int i = 1; i <= R; ++i)
	{
		for (int j = 1; j <= C; ++j)
		{
			if (board[i][j] != -1)
			{
				res += board[i][j];
			}
		}
	}

	cout << res;
}

으아… 이 문제는 총 두 시간이 걸렸다.

문제 해결

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <tuple>

using namespace std;

void setting();
void solve();
void spreadDustAll();
void spreadDust(int y, int x);
void OnAirPurification();
void UpAirPurification();
void UnderAirPurification();
void printBoard();

// 1. 미세먼지가 확산된다.
// 
// 
// 2. 공기청정기가 작동한다.
// 공청기 위아래를 알아야함.

struct SmallDust
{
	int y, x;
	int smallDust;
};

int R, C, T; // 행, 열, 시간
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
vector<vector<int>> board;
vector<pair<int, int>> dusts;
vector<SmallDust> smallDusts;
pair<int, int> upAirPurification, underAirPurification;
void setting()
{
	cin >> R >> C >> T;
	board = vector<vector<int>>(R + 1, vector<int>(C + 1));

	bool flag = false;
	for (int i = 1; i <= R; ++i)
	{
		for (int j = 1; j <= C; ++j)
		{
			cin >> board[i][j];
			if (board[i][j] != 0 && board[i][j] != -1)
				dusts.push_back({ i, j });
			if (board[i][j] == -1)
			{
				if (flag == false)
				{
					upAirPurification = { i, j };
					flag = true;
				}
				else
				{
					underAirPurification = { i , j };
				}
			}
		}
	}
}

void spreadDustAll()
{
	// 확산은 모든 칸에서 동시에 일어남.
	// 네 방향으로 확산.
	// 네 방향 중 공청있거나 칸없으면 확산 X
	// 확산의 양은 x/5, 소수점은 버림
	// 남은 미세먼지양은 (x - x/5 * 확산된 방향 수)

	for (int i = 0; i < dusts.size(); ++i)
	{
		spreadDust(dusts[i].first, dusts[i].second);
	}

	// TODO
	// smallDust들을 더해주기

	dusts.clear();
	for (int i = 0; i < smallDusts.size(); ++i)
	{
		board[smallDusts[i].y][smallDusts[i].x] += smallDusts[i].smallDust;
	}

	smallDusts.clear();
}

void spreadDust(int y, int x)
{
	// 확산은 모든 칸에서 동시에 일어남.
	// 네 방향으로 확산.
	// 네 방향 중 공청있거나 칸없으면 확산 X
	// 확산의 양은 x/5, 소수점은 버림
	// 남은 미세먼지양은 (x - x/5 * 확산된 방향 수)

	if (y == 3 && x == 7)
	{
		int a = 1;
	}
	if (y == 5 && x == 7)
	{
		int a = 1;
	}

	int cnt = 0;
	int smallDust = board[y][x] / 5;
	for (int i = 0; i < 4; ++i)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 1 || nx < 1 || ny > R || nx > C)
			continue;
		if (board[ny][nx] == -1)
			continue;

		cnt++;

		// TODO
		// 다 퍼진 뒤 더해줘야함.
		smallDusts.push_back({ ny, nx, smallDust });
		//board[ny][nx] += smallDust;
	}

	board[y][x] = board[y][x] - smallDust * cnt;
}

void OnAirPurification()
{
	UpAirPurification();
	UnderAirPurification();

	for (int i = 1; i <= R; ++i)
	{
		for (int j = 1; j <= C; ++j)
		{
			if (board[i][j] != 0 && board[i][j] != -1)
				dusts.push_back({ i, j });
		}
	}
}

void UpAirPurification()
{
	// 반시계 방향으로 순환함.

	// upAirPurification위치까지
	for (int i = upAirPurification.first - 1; i > 1; --i)
	{
		board[i][1] = board[i - 1][1];
	}

	// 왼쪽 벽까지
	for (int i = 1; i < C; ++i)
	{
		board[1][i] = board[1][i + 1];
	}

	// 위쪽 벽까지
	for (int i = 1; i < upAirPurification.first; ++i)
	{
		board[i][C] = board[i + 1][C];
	}

	// 오른쪽 벽까지 가기
	for (int i = C; i > 2; --i)
	{
		board[upAirPurification.first][i] = board[upAirPurification.first][i - 1];
	}
	board[upAirPurification.first][2] = 0;

}

void UnderAirPurification()
{
	// 시계 방향으로 순환함.

	// underAirPurification위치까지
	for (int i = underAirPurification.first + 1; i < R ; ++i)
	{
		board[i][1] = board[i + 1][1];
	}

	// 왼쪽 벽까지
	for (int i = 1; i < C; ++i)
	{
		board[R][i] = board[R][i + 1];
	}

	// 아래쪽 벽까지
	for (int i = R; i > underAirPurification.first; --i)
	{
		board[i][C] = board[i - 1][C];
	}

	// 오른쪽 벽까지 가기
	for (int i = C; i > 2; --i)
	{
		board[underAirPurification.first][i] = board[underAirPurification.first][i - 1];
	}
	board[underAirPurification.first][2] = 0;

}

void printBoard()
{
	for (int i = 1; i <= R; ++i)
	{
		for (int j = 1; j <= C; ++j)
		{
			cout << board[i][j] << " ";
		}
		cout << '\n';
	}

	cout << '\n';
}

void solve()
{
	setting();

	for (int i = 0; i < T; ++i)
	{
		spreadDustAll();

		OnAirPurification();
	}

	int res = 0;

	for (int i = 1; i <= R; ++i)
	{
		for (int j = 1; j <= C; ++j)
		{
			if (board[i][j] != -1)
			{
				res += board[i][j];
			}
		}
	}

	cout << res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

Twitter Facebook LinkedIn

BOJ 17144. 미세먼지 안녕!

🙇‍♀️[Gold IV] 미세먼지 안녕! - 17144

성능 요약

분류

제출 일자

문제 설명

입력

출력

🚀풀이

🚀전체 코드

공유하기

참고

BOJ 14620. 꽃길

BOJ 13301. 타일 장식물

BOJ 13301. 타일 장식물

BOJ 9934. 완전 이진 트리