17144. 미세먼지 안녕! GOLD V (C++)

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

17144번: 미세먼지 안녕!

문제

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

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
   • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
   • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
   • 확산되는 양은 Ar,c/5이고 소수점은 버린다.
   • (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
2. 공기청정기가 작동한다.
   • 공기청정기에서는 바람이 나온다.
   • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
   • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
   • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

다음은 확산의 예시이다.

왼쪽과 오른쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.

인접한 네 방향으로 모두 확산이 일어난다.

공기청정기가 있는 칸으로는 확산이 일어나지 않는다.

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

입력

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.

둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

출력

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

 

 

조건 하나 헷갈려서 두시간 가까이 걸렸다.

 

#include <iostream>
#include <cstring>
 
using namespace std;
int r,c,t,ans  , ux, uy, dx, dy;
int MAP[51][51], mx[] = {-1,0,1,0}, my[] = {0,1,0,-1},store[51][51];
bool up;
 
void spread()
{
    for(int aa=0;aa<r;aa++)
    {
        for(int bb=0;bb<c;bb++)
        {
            if(MAP[aa][bb] < 4) continue;
            int cnt = 0;
            for(int i=0;i<4;i++)
            {
                int nx = aa + mx[i];
                int ny = bb + my[i];
 
                if(nx<0 || ny<0 || nx>=r || ny>=c || MAP[nx][ny] == -1) continue;
                cnt++;// spread direction
            }
            int spread = MAP[aa][bb]/5;
            MAP[aa][bb] -= spread*cnt;
            for(int i=0;i<4;i++)
            {
                int nx = aa + mx[i];
                int ny = bb + my[i];
 
                if(nx<0 || ny<0 || nx>=r || ny>=c || MAP[nx][ny] == -1) continue;
                store[nx][ny] += spread;
            }
        }
    }
}
 
void add()
{
    for(int i=0;i<r;i++)
        for(int j=0;j<c;j++)
            MAP[i][j] += store[i][j];
 
}
//u,r,d,l
//r,u,l,d dir start 1, --,
void clean_up()
{
    int up[50][50];
    memset(up, 0, sizeof(up));
 
    for(int i = uy + 2;i<c;i++)
        up[ux][i] = MAP[ux][i-1];
 
    for(int i = ux - 1; i>=0; i--)
        up[i][c-1] = MAP[i + 1][c - 1];
 
    for(int i = c - 2;i>=0;i--)
        up[0][i] = MAP[0][i+1];
    for(int i=1;i<=ux;i++)
        up[i][0] = MAP[i-1][0];
 
    for(int i = 0;i<uy;i++)
        up[ux][i] = MAP[ux][i - 1];
 
 
    for(int i=0;i<c;i++)
    {
        if(MAP[0][i] != -1)
            MAP[0][i] = up[0][i];
        if(MAP[ux][i] != -1)
            MAP[ux][i] = up[ux][i];
    }
    for(int i=0;i<=ux;i++)
    {
        if(MAP[i][0] != -1)
            MAP[i][0] = up[i][0];
        if(MAP[i][c-1] != -1)
            MAP[i][c-1] = up[i][c-1];
    }
 
 
}
 
//r,d,l,u
void clean_down()
{
    int down[50][50];
    memset(down, 0, sizeof(down));
 
    for(int i = dy + 2;i<c;i++)
        down[dx][i] = MAP[dx][i-1];
    for(int i = dx + 1;i<r;i++)
        down[i][c-1] = MAP[i-1][c-1];
    for(int i = c - 2;i>=0;i--)
        down[r-1][i] = MAP[r-1][i+1];
    for(int i = r - 2 ;i>=dx;i--)
        down[i][0] = MAP[i+1][0];
 
    for(int i=0;i<c;i++)
    {
        if(MAP[r-1][i] != -1)
            MAP[r-1][i] = down[r-1][i];
        if(MAP[dx][i] != -1)
            MAP[dx][i] = down[dx][i];
    }
    for(int i=dx;i<r;i++)
    {
        if(MAP[i][0] != -1)
            MAP[i][0] = down[i][0];
        if(MAP[i][c-1] != -1)
            MAP[i][c-1] = down[i][c-1];
    }
 
 
 
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>r>>c>>t;
    for(int i=0;i<r;i++)
    {
        for(int j= 0 ;j<c;j++)
        {
            cin>>MAP[i][j];
            if(MAP[i][j] == -1 && !up)
            {
                ux = i, uy = j;
                up = true;
            }
            else if(MAP[i][j] == -1 && up)
                dx = i, dy = j;
        }
    }
 
    for(int i=0;i<t;i++)
    {
        memset(store, 0, sizeof(store));
        spread();
        add();
        clean_up();
        clean_down();
    }
 
    for(int i=0;i<r;i++)
        for(int j=0;j<c;j++)
            if(MAP[i][j] > 0)
                ans += MAP[i][j];
    cout<<ans<<'\n';
    return 0;
}
 

일단 코드가 되게 길고 알아보기 힘들거다.

내가 헷갈렸던 조건은 확산은 한꺼번에 이루어진다. 라는 조건이었는데 이걸 지키지 않고 미세먼지를 그냥 확산하면 뒤에 값은 커진채로 확산해 순서가 달라지게 된다.

이것을 해결하기 위해 확산 양을 저장하는 행렬을 하나 따로 만든다. 확산을 다 하고 그 다음에 두 행렬을 합쳐준다.

 

 그 다음에 한칸씩 민다. 이거는 반복문을 써서 하기 힘들거 같아 그냥 4개로 나눴다.

나름 BFS문제처럼 생겼지만 안쓰고 그냥 반복문으로 했다. 

 

자세한 알고리즘

1. 입력은 그냥 받는데 공기 청정기의 위 좌표와 아래 좌표를 기억해둔다.

 t시간동안 반복(2~6)

2. 확산 전 확산 양을 기록하는 store 행렬을 0으로 초기화

3  확산 단계

3 - 1 확산 양이 현재크기/5 이므로 4보다 작은것들은 안봐도 무방함.

3 - 2 4방향 탐색해서 가능한 곳 세고 store 행렬에 확산양 저장

4. 모든 확산이 끝난 후 기존 행렬과 store행렬 더하기

5. 위에 청소

5 - 1 그냥 밀기 어려우므로 밀린 값을 저장하는 행렬 하나 추가하고 0으로 초기화

5 - 2 4방향으로 돌면서 기존 행렬보다 한칸씩 밀리게 저장

5 - 3 밀린 부분만 덮어 쓰기 이때 공기청정기 위치 유의

6. 아래 청소

5와 동일한데 방향만 다름

 

7. 모든 행렬에서 0보다 큰값만 더하고 출력

 

시간도 오래 걸렸는데 메모리 효율도 별로고 시간도 좀 느리다.

다음 문제는 더 효율적으로 풀도록 노력하겠다.