본문 바로가기

카테고리 없음

BOJ 백준 17144 미세먼지 안녕!

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

 

17144번: 미세먼지 안녕!

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

www.acmicpc.net

문제 풀이)

 

    이 문제는 단계별로 생각하면 어렵지 않은 문제이다. 특히 결과를 직관적으로 확인할 수 있으므로, 한번 결과가

 

    원하는 로직대로 움직였다면 해결되는 문제가 아닐까 싶다.

 

    단계는, 문제 그대로 미세 먼지 확산 후 공기 청정기를 돌리는 것으로 나뉘어진다.

 

    1. 미세먼지 확산

 

    배열을 돌면서 미세먼지를 확인하면, 4방향으로 확산을 시켜준다. 문제를 보면 모든 미세먼지가 확산된 후에,

 

    확산된 값들이 각 장소에 저장되는 것을 알 수 있다.

 

    따라서 맵과 같은 배열 하나를 만들어주면 편하다. 새로 만든 배열해는 확산되는 미세먼지만 저장해 주고,

 

    실제 맵에는 미세 먼지를 확산시켰을 때 감소되는 양만 적용해 준다. 이러한 작업을 모두 마쳤다면,

 

    맵과 새로운 배열을 더해주면 된다.

 

    2. 공기 청정기    

 

    공기 청정기의 경로를 미리 벡터에 저장해주고, 공기청정기를 돌게 되면,

 

    벡터에 저장되어 있는 경로의 맵 값들을 덮어 씌어주면 된다.

 

    마지막으로 공기청정기의 진로 바로 앞에는 공기청정기의 값 -1이 오는데, 이를 0으로 초기화해주자.\

 

 

 

    소스 코드

...더보기

    

#include <cstdio>
#include <vector>

#define SIZE 55

using namespace std;

int r, c, t;
int map[SIZE][SIZE];

int xarr[4] = { 1, -1, 0, 0 };
int yarr[4] = { 0, 0, 1, -1 };

vector< pair<int, int> > vPath[2];

void CreatePath(int nRow, int nFlag, int nPathNum)
{
	int nCol = 0;
	int nTmpRow = nRow;

	// Right
	for ( ; nCol < c; ++nCol)
		vPath[nPathNum].push_back({ nTmpRow, nCol });
	nCol = c - 1;
	nTmpRow += nFlag;

	// Up or Down
	for (; nTmpRow >= 0 && nTmpRow < r; nTmpRow += nFlag)
		vPath[nPathNum].push_back({ nTmpRow, nCol });
	nTmpRow -= nFlag;
	nCol -= 1;

	// Left
	for (; nCol >= 0; --nCol)
		vPath[nPathNum].push_back({ nTmpRow, nCol });
	nCol = 0;
	nTmpRow -= nFlag;

	if (nFlag == -1)
	{
		// Down
		for ( ; nTmpRow < nRow; ++nTmpRow)
			vPath[nPathNum].push_back({ nTmpRow, nCol });
	}
	else
	{
		// Up
		for (; nTmpRow > nRow; --nTmpRow)
			vPath[nPathNum].push_back({ nTmpRow, nCol });
	}
}

void DiffusionCheck()
{
	int save[SIZE][SIZE] = { 0 };

	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			// 미세먼지인 경우
			if (map[i][j] != -1 && map[i][j] != 0)
			{
				// 확산된 방향
				int nCount = 0;
				// 한 타일에 확산될 양
				int nAmount = map[i][j] / 5;
				
				// 확산
				for (int k = 0; k < 4; ++k)
				{
					int next_x = i + xarr[k];
					int next_y = j + yarr[k];

					if (next_x < 0 || next_x >= r || next_y < 0 || next_y >= c) continue;
					if (map[next_x][next_y] == -1) continue;
					nCount++;
					save[next_x][next_y] += nAmount;
				}

				// 본래 자리 감소
				map[i][j] -= (nAmount * nCount);
			}
		}
	}

	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
			map[i][j] += save[i][j];
	}
}

void AirCleaner()
{
	int nIndex1 = vPath[0].size();
	int nIndex2 = vPath[1].size();

	for (int i = 0; i < nIndex1 - 1; ++i)
		map[vPath[0][nIndex1 - 1 - i].first][vPath[0][nIndex1 - 1 - i].second] = map[vPath[0][nIndex1 - 2 - i].first][vPath[0][nIndex1 - 2 - i].second];
	map[vPath[0][1].first][vPath[0][1].second] = 0;
	for (int i = 0; i < nIndex2 - 1; ++i)
		map[vPath[1][nIndex2 - 1 - i].first][vPath[1][nIndex2 - 1 - i].second] = map[vPath[1][nIndex2 - 2 - i].first][vPath[1][nIndex2 - 2 - i].second];
	map[vPath[1][1].first][vPath[1][1].second] = 0;
}

int main()
{
	int nCount = 0;
	
	scanf("%d %d %d", &r, &c, &t);
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			scanf("%d", &map[i][j]);
			if (map[i][j] == -1)
			{
				if (!nCount)
					CreatePath(i, -1, nCount);
				else
					CreatePath(i, 1, nCount);
				nCount++;
			}
		}
	}
	for (int i = 0; i < t; ++i)
	{
		DiffusionCheck();
		AirCleaner();
	}
	
	int nSum = 0;

	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			if (map[i][j] != -1)
				nSum += map[i][j];
		}
	}

	printf("%d\n", nSum);

	return 0;
}