[BOJ] 17144 미세먼지 안녕!

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

Note

미세먼지와 공치청정기가 있는 환경에서 미세먼지가 확산과 이동이 t번 반복 후 남아있는 미세먼지를 출력하자.

미세먼지가 퍼지는 방법, 공기청정기를 기준으로 공기의 이동까지 크게 예외를 생각할 부분이 없다.
미세먼지 확산 시 상하좌우를 확인 후, 미세먼지의 감소 양이 정해지고 상하좌우를 확인해 확산 할 수 있는 부분만 확산 하기 때문에 같은 코드가 두번 사용되는게 아쉬웠다.
미세먼지가 순차적으로 퍼지는게 아니라 동시에 퍼지기 때문에 이전 값을 기준으로 다음 값을 갱신해야한다. 즉 맵 전체를 복사하는 과정이 반복마다 필요하다.
공기청정기를 기준으로 공기 흐름이 만들어 지는건 어쩔 수 없이 일일히 처리 해야한다.

위 과정에 충실하게 구현하니 큰 예외처리가 필요하지 않았다.

알고리즘

1. 입력과 동시에 공기청정기의 상단 위치를 파악한다.
2. 주어진 t 변수만큼 확산과 대류를 반복한다.
   1. 맵 전체를 반복하되 0인 부분은 생략한다.
   2. 5 미만의 값을 가진 값은 그대로 복사한다.
   3. 5 이상의 값에 대해서는 확산을 실행한다.
   4. 확산이 실행된 후 공기 흐름에 따라 일부 미세먼지의 위치를 바꾼다.
3. 맵에 남아있는 미세먼지의 총 합을 출력한다.

소스코드

#include <iostream>

using namespace std;

const short MAX = 50;

const short posX[4] = { 1, 0, -1, 0 };
const short posY[4] = { 0, 1, 0, -1 };

short board[MAX][MAX];

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

	int row, col, time;
	int airCleanTop = -1, airCleanBottom;

	cin >> row >> col >> time;

	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++)
		{
			cin >> board[i][j];
			if (board[i][j] == -1 && airCleanTop == -1)
				airCleanTop = i;
		}
	}

	airCleanBottom = airCleanTop + 1;

	for (int tc = 0; tc < time; tc++) {
		short tempBoard[MAX][MAX];

		for (int i = 0; i < row; i++)
			for (int j = 0; j < col; j++)
			{
				tempBoard[i][j] = board[i][j];
				board[i][j] = 0;
			}

		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++)
			{
				if (!tempBoard[i][j])
					continue;

				if (tempBoard[i][j] < 5)
					board[i][j] += tempBoard[i][j];
				else
				{
					int count = 0;
					for (int k = 0; k < 4; k++) {
						int nextX = i + posX[k];
						int nextY = j + posY[k];
						if (0 <= nextX && nextX < row && 0 <= nextY && nextY < col && tempBoard[nextX][nextY] != -1)
							count++;
					}

					int spread = tempBoard[i][j] / 5;

					board[i][j] += tempBoard[i][j] - (spread * count);

					for (int k = 0; k < 4; k++) {
						int nextX = i + posX[k];
						int nextY = j + posY[k];
						if (0 <= nextX && nextX < row && 0 <= nextY && nextY < col && tempBoard[nextX][nextY] != -1)
							board[nextX][nextY] += spread;
					}
				}
			}
		}
		// Rotation
		// Top
		for (int i = airCleanTop - 1; i > 0; i--)
			board[i][0] = board[i - 1][0];
		for (int i = 0; i < col - 1; i++)
			board[0][i] = board[0][i + 1];
		for (int i = 0; i < airCleanTop; i++)
			board[i][col -1] = board[i + 1][col -1];
		for (int i = col - 1; i > 1; i--)
			board[airCleanTop][i] = board[airCleanTop][i - 1];

		// Bottom
		for (int i = airCleanBottom + 1; i < row - 1; i++)
			board[i][0] = board[i + 1][0];
		for (int i = 0; i < col - 1; i++)
			board[row - 1][i] = board[row - 1][i + 1];
		for (int i = row - 1; i > airCleanBottom; i--)
			board[i][col - 1] = board[i-1][col - 1];
		for (int i = col - 1; i > 1; i--)
			board[airCleanBottom][i] = board[airCleanBottom][i-1];

		board[airCleanTop][1] = board[airCleanBottom][1] = 0;
	}

	int res = 0;

	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++)
			if (board[i][j] > 0)
				res += board[i][j];

	cout << res;

	return 0;
}

2019-04-18 02:43:36에 Tistory에서 작성되었습니다.