https://www.acmicpc.net/problem/17144
문제 풀이)
이 문제는 단계별로 생각하면 어렵지 않은 문제이다. 특히 결과를 직관적으로 확인할 수 있으므로, 한번 결과가
원하는 로직대로 움직였다면 해결되는 문제가 아닐까 싶다.
단계는, 문제 그대로 미세 먼지 확산 후 공기 청정기를 돌리는 것으로 나뉘어진다.
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;
}