[Algorithm]Baekjoon 17144번 :: 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

#define MAX_NUM 0x3f3f3f3f
 
struct Node
{
    int y;
    int x;
    int dustAmount;
};
 
 
int r, c, t;
int arr[52][52] = { 0 };
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
int ccwDir[4][2] = { {0,1},{-1,0}, {0,-1},{1,0} };
int cwDir[4][2] = { {0,1}, {1,0}, {0,-1},{-1,0} };
 
Node upper; // 공기청정기 위쪽
Node lower; // 공기청정기 아래쪽
 
 
void diffuse()
{
    queue<Node> q;
 
    for (int i = 1; i <= r; i++)
    {
        for (int j = 1; j <= c; j++)
        {
            if (arr[i][j] >= 1)
            {
                q.push({ i,j,arr[i][j] });
            }
        }
    }
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        int curDustAmount = q.front().dustAmount;
 
        q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (arr[nextY][nextX] == MAX_NUM) continue;
            if (arr[nextY][nextX] == -1) continue; 
 
            arr[curY][curX] -= curDustAmount / 5;
            arr[nextY][nextX] += curDustAmount / 5;
        }
    }
}
 
void clean()
{
    int prevNum = 0;
    int curY = upper.y;
    int curX = upper.x + 1;
    int dirIndex = 0;
 
    while (arr[curY][curX] != -1) // 반시계방향
    {
        int temp = arr[curY][curX];
        arr[curY][curX] = prevNum;
        prevNum = temp;
 
        if (arr[curY + ccwDir[dirIndex][0]][curX + ccwDir[dirIndex][1]] == MAX_NUM)
        {
            dirIndex++;
        }
         
        curY += ccwDir[dirIndex][0];
        curX += ccwDir[dirIndex][1];
    }
 
    prevNum = 0;
    curY = lower.y;
    curX = lower.x + 1;
    dirIndex = 0;
 
    while (arr[curY][curX] != -1) // 시계방향
    {
        int temp = arr[curY][curX];
        arr[curY][curX] = prevNum;
        prevNum = temp;
 
        if (arr[curY + cwDir[dirIndex][0]][curX + cwDir[dirIndex][1]] == MAX_NUM)
        {
            dirIndex++;
        }
 
        curY += cwDir[dirIndex][0];
        curX += cwDir[dirIndex][1];
    }
 
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> r >> c >> t;
 
    int check = false;
    memset(arr, 0x3f, sizeof(arr));
 
    for (int i = 1; i <= r; i++)
    {
        for (int j = 1; j <= c; j++)
        {
            cin >> arr[i][j];
 
            if (arr[i][j] == -1)
            {
                if (!check)
                {
                    upper = { i,j };
                    check = true;
                }
                else
                {
                    lower = { i,j };
                }
            }
        }
    }
 
    for (int i = 0; i < t; i++)
    {
        diffuse();
        clean();
    }
 
    int result = 0;
 
    for (int i = 1; i <= r; i++)
    {
        for (int j = 1; j <= c; j++)
        {
            if (arr[i][j] >= 1)
            {
                result += arr[i][j];
            }
        }
    }
 
    cout << result;
}

 

이 문제에서는 먼지가 확산하는 단계에서 헷갈리지 않는게 가장 중요하다.

순차적으로 확산하는게 아니라, 한번에 확산하는 것이다.

즉 0,0에서 확산이 된다면 인접한공간에 먼지가 추가될 텐데, 그 추가된것을 합한다음 퍼뜨리면 안된다.

 

0,0이 15이고 0,1은 5라고 가정하다.

0,0에서는 0,1로만 확산할 수 있다고 또 가정한다.

 

그러면 0,0에서 먼저 확산처리를 한다면 0,0은 12가 될 것이고 0,1에 +3만큼 퍼질것이다.

그러면 0,1이 5+3이 되서 8이 될텐데, 여기서 0,1의 확산처리를 할 때 이 8값을 기준으로 확산처리를 하면 안된다.

0,0에서의 확산으로인한 +3이 추가되기 '이전'인 5를 기준으로 확산처리해야한다.

즉, 인접한곳에서 확산된 먼지로인한 누적값은 마지막에 합산을 해야하고, 확산처리를 할 땐 초기배열값으로 하면 된다고 생각해야 한다.

 

그렇기 때문에 먼저 각 배열의 노드를 큐에 담아서 기존의 값을 보관해준다. (반드시 보장해줘야 한다.)

그런다음 큐에서 노드를 하나씩 꺼내서 주변에 먼지를 뿌린 후, 해당 노드의 위치에 해당하는 arr위치에는 뿌린값만큼 -를 해주고 뿌린 위치에 해당하는 arr위치에는 합연산을 해준다.

 

뿌리는 값에 대한 기준은 미리 큐에 보관했던 기존의 값으로 뿌리는 것이기 때문에 arr에 바로 적용해도 된다.

 

이후 공기청정기 정화작업을 해줘야하는데 나같은 경우 반시계방향의 dir배열(ccwDir)과 시계방향의 dir배열(cwDir)을 만들어줘서 방향을 꺾으면서 탐색했다.

 

이건 약간 미세팁인데, 배열을 만들 때 행과 열에 +2씩 해서 한겹을 더 둘러싼 다음, 해당 한겹의 원소값들에는 쓰레기값들을 넣어놓으면 배열의 유효범위체크할 때 편하다.