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

www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

풀어도 풀어도 오래 걸리는 구현 문제! 이번엔 bfs나 dfs는 사용하지 않았다. 순수 구현

 

1. 미세먼지가 퍼진다.

2. 공기청정기가 돌아간다. 순서이다.

 

1은 다시

1-1 현재 위치에 미세먼지가 있다면

1-2  dust배열에 위아래오른쪽왼쪽 가능한 곳에 미세먼지양/5를 퍼트리고 arr배열에서 현재 위치의 미세먼지 양을 줄인다.

1-3 arr += dust

 

2는 공기청정기를 사용하여 공기를 순환시키는 것으로 위쪽은 시계 반대방향

아래쪽은 시계방향으로 미세먼지가 이동한다. 공기 청정기에 들어간 미세먼지는 정화되므로 공기 청정기 주변은 무조건 미세먼지 0이 된다.

#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;
int arr[50][50];
int dust[50][50];
int r, c, t;

int dr[4] = {0, 0, -1, 1};
int dc[4] = {1, -1, 0, 0};

vector<pair<int, int>> cleaner;

void diffuseDust()
{
  for (int i = 0; i < r; i++)
  {
    for (int j = 0; j < c; j++)
    {
      if (arr[i][j] == 0)
        continue;

      int num = 0;

      for (int k = 0; k < 4; k++)
      {
        int nextR = i + dr[k];
        int nextC = j + dc[k];

        if (nextR < 0 || nextC < 0 || nextR > r - 1 || nextC > c - 1 || arr[nextR][nextC] == -1)
        {
          continue;
        }

        dust[nextR][nextC] += arr[i][j] / 5;
        num++;
      }

      arr[i][j] -= arr[i][j] / 5 * num;
    }
  }

  for (int i = 0; i < r; i++)
  {
    for (int j = 0; j < c; j++)
    {
      arr[i][j] += dust[i][j];
    }
  }
}

void cleanDust()
{
  //up
  int upR = cleaner[0].first;
  int downR = cleaner[1].first;
  for (int row = upR - 2; row > -1; row--)
  {
    arr[row + 1][0] = arr[row][0];
  }

  for (int col = 1; col < c; col++)
  {
    arr[0][col - 1] = arr[0][col];
  }

  for (int row = 1; row < downR; row++)
  {
    arr[row - 1][c - 1] = arr[row][c - 1];
  }

  for (int col = c - 2; col > 0; col--)
  {
    arr[upR][col + 1] = arr[upR][col];
  }

  //down
  for (int row = downR + 2; row < r; row++)
  {
    arr[row - 1][0] = arr[row][0];
  }

  for (int col = 1; col < c; col++)
  {
    arr[r - 1][col - 1] = arr[r - 1][col];
  }

  for (int row = r - 2; row > upR; row--)
  {
    arr[row + 1][c - 1] = arr[row][c - 1];
  }

  for (int col = c - 2; col > 0; col--)
  {
    arr[downR][col + 1] = arr[downR][col];
  }

  arr[upR][1] = arr[downR][1] = 0;
}

int main(void)
{
  scanf("%d%d%d", &r, &c, &t);
  for (int i = 0; i < r; i++)
  {
    for (int j = 0; j < c; j++)
    {
      scanf("%d", &arr[i][j]);
      if (arr[i][j] == -1)
      {
        cleaner.push_back(make_pair(i, j));
      }
    }
  }

  while (t--)
  {
    memset(dust, 0, sizeof(dust));
    diffuseDust();
    cleanDust();
  }

  int result = 0;
  for (int i = 0; i < r; i++)
  {
    for (int j = 0; j < c; j++)
    {
      result += arr[i][j];
    }
  }

  printf("%d\n", result + 2);
  return 0;
}