[ 백준 17144 ] 미세먼지 안녕 !

문제

미세먼지 안녕 !

문제 설명

• 미세먼지 확산

미세먼지가 있는 칸은 배열을 넘지 않으면서 공기 청정기를 피해 확산이 된다.

한칸에 있는 미세먼지가 확산을 하자마자 확산된 미세먼지 값을 추가 시켜버리면 기존의 미세먼지 양이 변경되므로 한칸당 미세먼지의 실제값과 확산에 의해 추가된 양을 동시에 갖고 있어야 한다. 그래야 한번의 확산과정이 끝나고 배열 전체를 돌면서 추가된 양을 실제값에 더해주면 된다.

 

또한, 미세먼지가 확산이 되고 남은 미세먼지의 양을 계산할 때 확산이 얼만큼 됬는지도 알아야 하기 때문에 확산된 칸수도 갖고 있도록 한다.

 

미세먼지 확산 과정을 구체적으로 알아보도록 하자.

1. 배열을 처음부터 탐색을 한다
2. 미세먼지가 존재한다면
3. 상하좌우로 배열을 넘지 않고, 공기 청정기를 피해서 미세먼지 값을 확산 시킨다
4. 3번의 과정이 끝났다면, 현재 미세먼지 칸(?)의 값을 변경시키고 확산된 칸수(cnt)을 초기화한다.
5. 1번의 과정이 모두 끝났다면 배열을 처음부터 탐색하면서 확산에 의해 추가된 양을 미세먼지의 실제값에 더해주면 된다.

 

1번에서 5번까지의 과정이 1초동안 일어난다.

 

void DDust()
{
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            if (arr[i][j].amount > 0)
            {
                for (int k = 0; k < 4; k++)
                {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if (x > -1 && x<R && y>-1 && y < C && arr[x][y].amount != -1)
                    {
                        arr[x][y].add += (arr[i][j].amount / 5);//확산값 add
                        arr[i][j].cnt++;
                    }
                }
                arr[i][j].amount = arr[i][j].amount - ((arr[i][j].amount / 5)*arr[i][j].cnt);
                arr[i][j].cnt = 0;
            }
        }
    }
    //add 값 amount에 추가해주고 add 값 0 
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            arr[i][j].amount += arr[i][j].add;
            arr[i][j].add = 0;
        }
    }
}

 

공기를 순환시켜보자.

공기 청정기의 좌표를 queue pair 을 이용해 좌표 순서쌍으로 담아주었다.

• 공기 청정기의 위쪽 -> 반시계 방향 이동

 

반시계 방향으로 이동하기 전에 공기 청정기의 위의 칸에 미세먼지를 -1 로 변경시킨다.

그 이유는 미세먼지를 변경시키지 않으면 공기청정기의 값이 미세먼지 값으로 바뀌게 되어 먼지 확산 과정에서 공기청정기를 미세먼지로 잘못 인식할 수 있기 때문이다.

 

이동을 할때에는 (위의 그림에서) start 지점부터 반시계 방향을 따라가면서 up_dx , up_dy 배열에 맞게 이동을 해주면 된다.

이 배열안에는 { 상 , 우 , 하 , 좌 } 의 순서가 담겨 있다.

 

모두 이동을 한 후 미세먼지가 이동을 했으니 마지막 칸 즉 , 공기청정기 옆 칸을 0으로 만들어 주어야 한다.

 

• 공기 청정기의 아래쪽 -> 시계 방향 이동

시계 방향으로 이동하기 전에 공기 청정기의 아래의 칸에 미세먼지를 -1 로 변경시킨다.

그러고 다음은 위의 과정과 거의 똑같이 하면 된다.

변경해야 할 것은 이동을 할때에 배열 안을 { 하 , 우 , 상 , 좌} 로 담고 가로 방향을 바꾸어 줄때 for size만 변경하면 된다.

 

구현

​x
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
using namespace std;
​
typedef struct {
    int amount = 0;//실제양
    int add = 0;//확산되는 미세먼지 값
    int cnt = 0;//확산된 칸
}Dust;
​
static int R, C, T;
​
Dust arr[51][51];
queue <pair<int, int>> Robot;
​
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
​
int up_dx[4] = { -1,0,1,0 };
int up_dy[4] = { 0,1,0,-1 };
​
int down_dx[4] = { 1,0,-1,0 };
int down_dy[4] = { 0,1,0,-1 };
​
void Input()
{
    cin >> R >> C >> T;
    int data = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> data;
            arr[i][j].amount = data;
            if (data == -1)
                Robot.push(make_pair(i, j));
        }
    }           
}
​
void DDust()
{
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            if (arr[i][j].amount > 0)
            {
                for (int k = 0; k < 4; k++)
                {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if (x > -1 && x<R && y>-1 && y < C && arr[x][y].amount != -1)
                    {
                        arr[x][y].add += (arr[i][j].amount / 5);//확산값 add
                        arr[i][j].cnt++;
                    }
                }
                arr[i][j].amount = arr[i][j].amount - ((arr[i][j].amount / 5)*arr[i][j].cnt);
                arr[i][j].cnt = 0;
            }
        }
    }
    //add 값 amount에 추가해주고 add 값 0 
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            arr[i][j].amount += arr[i][j].add;
            arr[i][j].add = 0;
        }
    }
}
void UP()
{
    int up_x = Robot.front().first;
    int up_y = Robot.front().second;
    int size = Robot.front().first;
​
    arr[up_x - 1][up_y].amount = -1;
​
    for (int i = 0; i < 4; i++)
    {
        if (i % 2 == 0)
        {
            for (int a = 0; a < size; a++)
            {
                arr[up_x][up_y] = arr[up_x + up_dx[i]][up_y + up_dy[i]];
                up_x = up_x + up_dx[i];
                up_y = up_y + up_dy[i];
            }
        }
        else
        {
            for (int a = 0; a < C - 1; a++)
            {
                arr[up_x][up_y] = arr[up_x + up_dx[i]][up_y + up_dy[i]];
                up_x = up_x + up_dx[i];
                up_y = up_y + up_dy[i];
            }
        }
    }
    arr[up_x][up_y + 1].amount = 0;
}
​
void DOWN()
{
    int down_x = Robot.back().first;
    int down_y = Robot.back().second;
    int size = Robot.back().first;
​
    arr[down_x + 1][down_y].amount = -1;
​
    for (int i = 0; i < 4; i++)
    {
        if (i % 2 == 0)
        {
            for (int a = 0; a < R-size-1; a++)
            {
                arr[down_x][down_y] = arr[down_x + down_dx[i]][down_y + down_dy[i]];
                down_x = down_x + down_dx[i];
                down_y = down_y + down_dy[i];
            }
        }
        else
        {
            for (int a = 0; a < C - 1; a++)
            {
                arr[down_x][down_y] = arr[down_x + down_dx[i]][down_y + down_dy[i]];
                down_x = down_x + down_dx[i];
                down_y = down_y + down_dy[i];
            }
        }
    }
    arr[down_x][down_y + 1].amount = 0;
}
void Air()
{
    UP();
    DOWN();
}
​
int Answer()
{
    int cnt = 0;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            if (arr[i][j].amount > 0)cnt += arr[i][j].amount;
​
    return cnt;
}
​
void Solve()
{
    Input();
    for (int i=0; i < T; i++)
    {
        DDust();
        Air();
    }
    cout << Answer();
}
​
int main()
{
    Solve();
}