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

문제설명

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

1x1크기의 칸 RxC 크기의 집에 공기청정기는 항상 1번 열에 설치되어 있고 크기는 두 행을 차지한다.
각 칸에는 미세먼지의 양이 표시된다.

1. 미세먼지 확산

• (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
• 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
• 확산되는 양은 Ar,c/5이고 소수점은 버린다.
• (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.

2. 공기청정기 작동

• 공기청정기에서는 바람이 나온다.
• 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
• 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
• 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.
  

입력
첫째 줄에 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초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

풀이

미세먼지 확산

1. 초기 미세먼지 정보: 2차원 배열 a
2. a[y][x]의 값이 -1,0이 아니고 visited가 0이면 DFS를 이용해서 4방향을 탐색한다.

void move(int y, int x, int c)

3. 주변 칸 a[ny][nx]에 더해지는 미세먼저 Ar,c/5는 2차원 배열 tmp[ny][nx]에 더한다.
   퍼질 수 있는 방향 개수 : c

tmp[ny][nx] += (a[y][x] / 5);
c++;

4. 4방향 탐색이 종료되면 확산 후 남은 미세먼지 양을 tmp[y][x]에 더해준다.

tmp[y][x] += (a[y][x] - (a[y][x] / 5) * c);

공기청정기 작동

각 모서리에 도달하면 wind 함수의 방향을 바꿔서 호출

코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, t, a[51][51], tmp[51][51], visited[51][51], gx1, gy1, gx2, gy2, cnt, res;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, -1, 0, 1};
void move(int y, int x, int c)
{
    visited[y][x] = 1;
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 1 || nx < 1 || ny > n || nx > m || a[ny][nx] == -1)
            continue;
        c++;
        tmp[ny][nx] += (a[y][x] / 5);
        if (!visited[ny][nx])
            move(ny, nx, 0);
    }

    tmp[y][x] += (a[y][x] - (a[y][x] / 5) * c);
    return;
}

void wind(int y, int x, int mod, int d)
{
    int ny, nx;
    if (mod == 1)
    {
        ny = y;
        nx = x + 1;
        if (nx == m)
        {
            if (d == 0)
                wind(ny, nx, 2, d);
            else
                wind(ny, nx, 4, d);
        }
        else
            wind(ny, nx, 1, d);
    }

    if (mod == 2)
    {
        ny = y - 1;
        nx = x;
        if (ny == 1)
            wind(ny, nx, 3, d);
        else if (ny == gy2)
            return;

        else
            wind(ny, nx, 2, d);
    }
    if (mod == 3)
    {
        ny = y;
        nx = x - 1;
        if (nx == gx1)
        {
            if (d == 0)
                wind(ny, nx, 4, d);
            else
                wind(ny, nx, 2, d);
        }
        else
            wind(ny, nx, 3, d);
    }
    if (mod == 4)
    {
        ny = y + 1;
        nx = x;
        if (ny == gy1)
            return;

        else if (ny == n)
            wind(ny, nx, 3, d);

        else
            wind(ny, nx, 4, d);
    }
    tmp[ny][nx] = tmp[y][x];
    if (tmp[ny][nx] == -1)
        tmp[ny][nx] = 0;
}

int main()
{
    cin >> n >> m >> t;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            if (a[i][j] == -1)
            {
                if (!cnt)
                {
                    gx1 = j;
                    gy1 = i;
                }
                else
                {
                    gx2 = j;
                    gy2 = i;
                }
                cnt++;
            }
        }
    }

    while (t--)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (a[i][j] == -1)
                    tmp[i][j] = -1;
                else if (a[i][j] != 0 && !visited[i][j])
                    move(i, j, 0);
            }
        }

        wind(gy1, gx1, 1, 0);
        wind(gy2, gx2, 1, 1);
        if (t == 0)
            break;
        fill(&visited[0][0], &visited[0][0] + 51 * 51, 0);
        copy(&tmp[0][0], &tmp[0][0] + 51 * 51, &a[0][0]);
        fill(&tmp[0][0], &tmp[0][0] + 51 * 51, 0);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            res += tmp[i][j];
        }
    }
    cout << res + 2 << "\n";
}