백준 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초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

문제를 보고 든 생각

• 이동 전 먼지와 이동 후 먼지를 저장하는 이차원 배열을 두 개 만들어서 분리시켜야겠다. (동시에 흩뿌려지므로)
• 공기 순환은 그냥 반복문 돌리면 되겠다.
• 함수를 잘 나눠보자.

풀이 간단 설명

1. copyDustMap, moveDust, clearDust, copyScatteredMap 함수를 순서대로 사용했다.

코드

#include <iostream>
#include <vector>

#define MAX_N 50

using namespace std;

struct pos{
  int r, c;
};


int R, C, T;
int dustMap[MAX_N+1][MAX_N+1];
int scatteredMap[MAX_N+1][MAX_N+1];
int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
pos upPos, downPos;

void getInput(){
  vector<pos> cleaner;
  cin >> R >> C >> T;
  for(int r=1; r<=R; ++r){
    for(int c=1; c<=C; ++c){
      cin >> dustMap[r][c];
      if(dustMap[r][c] == -1){
        cleaner.push_back({r, c});
      }
    }
  }
  upPos = cleaner[0];
  downPos = cleaner[1];
}

void copyDustMap(){
  for(int r=1; r<=R; ++r){
    for(int c=1; c<=C; ++c){
      scatteredMap[r][c] = dustMap[r][c];
    }
  }
}

void copyScatteredMap(){
  for(int r=1; r<=R; ++r){
    for(int c=1; c<=C; ++c){
      dustMap[r][c] = scatteredMap[r][c];
    }
  }
}

bool boundCheck(int r, int c){
  return (r < 1 || c < 1 || r > R || c > C);
}

void moveDust(){
  for(int r=1; r<=R; ++r){
    for(int c=1; c<=C; ++c){
      if(dustMap[r][c] == 0){
        // no dust
        continue;
      }

      const int dust = dustMap[r][c]/5;
      int scattered = 0;
      if(dust == 0){
        // no dust to move
        continue;
      }
      for(int i=0; i<4; ++i){
        int nr = r + dir[i][0];
        int nc = c + dir[i][1];
        if(boundCheck(nr, nc)){
          // out of bound
          continue;
        }
        if(dustMap[nr][nc] == -1){
          // cleaner exist
          continue;
        }
        scatteredMap[nr][nc] += dust;
        scattered += dust;
      }
      scatteredMap[r][c] -= scattered;
    }
  }
}

void upClear(){
  int r = upPos.r;
  int c = upPos.c;
  scatteredMap[r-1][c] = 0;
  --r;
  while(r > 1){
    scatteredMap[r][c] = scatteredMap[r-1][c];
    --r;
  }
  // r = 1

  while(c < C){
    scatteredMap[r][c] = scatteredMap[r][c+1];
    ++c;
  }
  // r = 1, c = C

  while(r < upPos.r){
    scatteredMap[r][c] = scatteredMap[r+1][c];
    ++r;
  }
  // r = upPos.r, c = C

  while(1 < c){
    scatteredMap[r][c] = scatteredMap[r][c-1];
    --c;
  }
  // r = upPos.r, c = 1

  scatteredMap[r][c+1] = 0;
}

void downClear(){
  int r = downPos.r;
  int c = downPos.c;
  scatteredMap[r+1][c] = 0;
  ++r;

  while(r < R){
    scatteredMap[r][c] = scatteredMap[r+1][c];
    ++r;
  }
  // r = R

  while(c < C){
    scatteredMap[r][c] = scatteredMap[r][c+1];
    ++c;
  }
  // c = C;

  while(r > downPos.r){
    scatteredMap[r][c] = scatteredMap[r-1][c];
    --r;
  }
  // r = downPos.r
  
  while(c > 1){
    scatteredMap[r][c] = scatteredMap[r][c-1];
    --c;
  }
  // r = downPos.r, c = 1
  
  scatteredMap[r][c+1] = 0;
}

void clearDust(){
  upClear();
  downClear();
}

int countDust(){
  int cnt = 0;
  for(int i=1; i<=R; ++i){
    for(int j=1; j<=C; ++j){
      if(dustMap[i][j] == -1){
        continue;
      }
      if(dustMap[i][j]){
        cnt += dustMap[i][j];
      }
    }
  }

  return cnt;
}

void solve(){
  getInput();
  while(T--){
    copyDustMap();
    moveDust();
    clearDust();
    copyScatteredMap();
  }

  cout << countDust();
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();

  return 0;
}