[백준 / BAEKJOON] 17144번 미세먼지 안녕! - C++

문제 원문

조건

시간 제한 : 1초
메모리 제한 : 512 MB

문제

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 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초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

예제

풀이

주어진 기능을 구현하는 시뮬레이션 문제입니다.

이런 문제는 단순히 코드를 나열하면서 구현하게되면 작성하다가 햇갈리기 때문에 클래스를 구성하여 풀었습니다.

클래스는 방의 크기만 생성자로 입력받고 나머지 입력은 자체적으로 받습니다.

그 후 T의 크기 만큼 정해진 시퀀스를 수행하고 결과를 반환합니다.

풀이 과정은 다음과 같습니다.

1. 클래스 내부에 확산 기능과 공기청정기 작동 기능을 구현
   1. 확산 기능은 임시 변수를 만들어 확산한 결과를 구하고 기존 변수에 삽입
   2. 공기청정기는 위쪽과 아래쪽 동작을 각각 함수로 구현하여 동작 이때 총 미세먼지의 양이 변하기 때문에 반영해 준다.
2. 주어진 T만큼 반복 후 남아있는 결과 반환

성공 코드

#include <iostream>
#include <vector>

using namespace std;

//define

using ull = unsigned long long ;
using location =  pair<int, int> ;
using matrix = vector<vector<int>>;
const int DIRECTION = 4;

//custum function
class Solution
{
	//1. 미세먼지 확산
	//2. 공기청정기 작동

private:
	const int moveX[DIRECTION] = { 1, -1, 0, 0 };
	const int moveY[DIRECTION] = { 0, 0, 1, -1 };
	const int topSizeMoveX[DIRECTION] = { -1, 0, 1, 0 };
	const int topSizeMoveY[DIRECTION] = { 0, 1, 0, -1 };
	const int bottomSizeMoveX[DIRECTION] = { 1, 0, -1, 0 };
	const int bottomSizeMoveY[DIRECTION] = { 0, 1, 0, -1 };
	int sizeX, sizeY, airCleanerPos, sumVal;
	
	matrix room;

	void init()
	{
		airCleanerPos = -1;
		room = matrix(sizeX, vector<int>(sizeY));
		sumVal = 0;
	}

	void diffusion()
	{
		matrix tempRoom(sizeX, vector<int>(sizeY));
		tempRoom[airCleanerPos][0] = -1;
		tempRoom[airCleanerPos + 1][0] = -1;

		//확산
		for (int x(0); x < sizeX; ++x)
		{
			for (int y(0); y < sizeY; ++y)
			{
				if (room[x][y] > 0)
				{
					//기존값 복사후 확산되는 칸 마다 값을 뺀다
					tempRoom[x][y] += room[x][y];
					int diffusionVal = int(room[x][y] / 5);					

					//인접한 4방향으로 확산되나
					for (int dir(0); dir < DIRECTION; ++dir)
					{
						int posX(x + moveX[dir]), posY(y + moveY[dir]);
						//공기청정기가 있거나 칸이 없으면 확산되지 않는다
						if (posX >= 0 && posX < sizeX && posY >= 0 && posY < sizeY && room[posX][posY] != -1)
						{
							tempRoom[posX][posY] += diffusionVal;
							tempRoom[x][y] -= diffusionVal;
						}
					}
				}
			}
		}

		room = tempRoom;
	}

	void airCleanerRun()
	{
		//위쪽 공기청정기는 반시계 아래는 시계
		//바람의 방향대로 모두 한 칸씩 이동하고
		//공기청정기로 들어간 미세먼지는 정화된다
		topSideWindRun();
		bottomSideWindRun();
	}

	void topSideWindRun()
	{
		//공기청정기 바로 위 부터
		int nowX(airCleanerPos - 1), nowY(0);
		int dir(0);
		//정화되는 먼지
		sumVal -= room[nowX][nowY];
		//역순으로 값을 이동한다
		while (true)
		{
			int posX(nowX + topSizeMoveX[dir]), posY(nowY + topSizeMoveY[dir]);

			//만약 범위에 벗어난다면 방향을 바꾼다
			if (posX < 0 || posY < 0 || posX > airCleanerPos || posY >= sizeY)
			{
				++dir;
				continue;
			}

			if (room[posX][posY] == -1)
			{
				room[nowX][nowY] = 0;
				break;
			}

			room[nowX][nowY] = room[posX][posY];
			nowX = posX;
			nowY = posY;
		}
	}

	void bottomSideWindRun()
	{
		//공기청정기 바로 위 부터
		int nowX(airCleanerPos + 2), nowY(0);
		int dir(0);
		//정화되는 먼지
		sumVal -= room[nowX][nowY];
		//역순으로 값을 이동한다
		while (true)
		{
			int posX(nowX + bottomSizeMoveX[dir]), posY(nowY + bottomSizeMoveY[dir]);

			//만약 범위에 벗어난다면 방향을 바꾼다
			if (posX <= airCleanerPos || posY < 0 || posX >= sizeX || posY >= sizeY)
			{
				++dir;
				continue;
			}

			if (room[posX][posY] == -1)
			{
				room[nowX][nowY] = 0;
				break;
			}

			room[nowX][nowY] = room[posX][posY];
			nowX = posX;
			nowY = posY;
		}
	}

public:
	Solution(int sizeX, int sizeY)
	{
		this->sizeX = sizeX;
		this->sizeY = sizeY;
		init();
	}

	void roomInput()
	{
		for (int x(0); x < sizeX; ++x)
		{
			for (int y(0); y < sizeY; ++y)
			{
				cin >> room[x][y];
				if (room[x][y] == -1 && airCleanerPos == -1)
				{
					airCleanerPos = x;
				}
				else if (room[x][y] > 0)
				{
					sumVal += room[x][y];
				}
			}
		}
	}

	int solution(int runTime)
	{
		for (int time(0); time < runTime; ++time)
		{
			diffusion();
			airCleanerRun();
		}

		return sumVal;
	}
};

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	////////////////////////////////////
	//Declaration
	int sizeX(0), sizeY(0), time(0), airCleanerPos(-1);
	cin >> sizeX >> sizeY >> time;
	
	//Solution
	Solution sol(sizeX, sizeY);
	sol.roomInput();

	//Output
	cout << sol.solution(time) << '\n';

	return 0;
}

결과

Github - github.com/ledpear