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

17144번 미세먼지 안녕!

---

1. 이해하기

• 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다.
• 공기청정기가 설치되어 있지 않은 칸에 미세먼지가 있다.
• 이때 1초 동안 일어나는 일
  1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
     • 미세먼지는 인접한 네 방향으로 확산된다.
     • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
     • 확산되는 양은 (미세먼지 양)/5이고 소수점은 버린다.
     • 그 자리에 남은 미세먼지 양은 (미세먼지 양)-(미세먼지 양/5)*(확산된 방향의 개수) 이다.
  2. 공기청정기가 작동한다.
     • 공기청정기에서는 바람이 나온다.
     • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
     • 바람이 불면 미세먼지가 바람의 방향대로 한 칸씩 이동한다.
     • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.
• T초가 지난 후 미세먼지의 양을 구한다.
• 시뮬레이션 문제.

---

2. 구현하기

• 미세먼지의 확산.

  • 미세먼지의 확산을 구현하기 위해서 임시배열을 하나 만들고 일어나는 변화는 임시배열에 저장한다.

  bool can_not_spread(int x, int y) {
      return x < 0 or x >= R or y < 0 or y >= C
      or (cleaner[0].x == x and cleaner[0].y == y) or (cleaner[1].x == x and cleaner[1].y == y);
  }
  
  void copy_copy_map(int copy_map[50][50]) {
      for(int i = 0; i < R; i++) {
          for(int j = 0; j < C; j++) {
              map[i][j] = copy_map[i][j];
          }
      }
  }
  
  void spread() {
      int copy_map[50][50] = {0,};
      for(int i = 0; i < R; i++) {
          for(int j = 0; j < C; j++) {
              if(map[i][j] <= 0) continue;
              int cnt = 0;
              for(int d = 0; d < 4; d++) {
                  int nx = i+dx[d], ny = j+dy[d];
                  if(can_not_spread(nx,ny)) continue;
                  copy_map[nx][ny] += map[i][j]/5;
                  cnt++;
              }
              copy_map[i][j] += map[i][j]-((map[i][j]/5)*cnt);
          }
      }
      copy_copy_map(copy_map);
  }

• 공기청정기의 작동.

  • 위쪽 공기청정기와 아래쪽 공기청정기의 작동을 구현한다.

  void clean() {
      int sx = cleaner[0].x, sy = cleaner[0].y+1;
      int before = 0, after;
      // right
      while(sy < C) {
          after = map[sx][sy];
          map[sx][sy] = before;
          before = after;
          sy++;
      }
      sy--;
      // up
      sx--;
      while(sx >= 0) {
          after = map[sx][sy];
          map[sx][sy] = before;
          before = after;
          sx--;
      }
      sx++;
      // left
      sy--;
      while(sy >= 0) {
          after = map[sx][sy];
          map[sx][sy] = before;
          before = after;
          sy--;
      }
      sy++;
      // down
      sx++;
      while(sx < cleaner[0].x) {
          after = map[sx][sy];
          map[sx][sy] = before;
          before = after;
          sx++;
      }
  
      sx = cleaner[1].x; sy = cleaner[1].y+1;
      before = 0;
      // right
      while(sy < C) {
          after = map[sx][sy];
          map[sx][sy] = before;
          before = after;
          sy++;
      }
      sy--;
      // down
      sx++;
      while(sx < R) {
          after = map[sx][sy];
          map[sx][sy] = before;
          before = after;
          sx++;
      }
      sx--;
      // left
      sy--;
      while(sy >= 0) {
          after = map[sx][sy];
          map[sx][sy] = before;
          before = after;
          sy--;
      }
      sy++;
      // up
      sx--;
      while(sx > cleaner[1].x) {
          after = map[sx][sy];
          map[sx][sy] = before;
          before = after;
          sx--;
      }
  }

• T초가 지날때까지 미세먼지 확산과 공기청정기를 작동시키고, 이후에 미세먼지의 양을 구한다.

  int count_dust() {
      int ret = 0;
      for(int i = 0; i < R; i++) {
          for(int j = 0; j < C; j++) {
              if(map[i][j] == -1) continue;
              ret += map[i][j];
          }
      }
      return ret;
  }
  
  int simulate() {
      for(int i = 0; i < T; i++) {
          spread();
          clean();
      }
      return count_dust();
  }

---

3. 전체 코드

#include <iostream>
using namespace std;
struct Point{
    int x,y;
};
int map[50][50];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
Point cleaner[2];
int R,C,T;

bool can_not_spread(int x, int y) {
    return x < 0 or x >= R or y < 0 or y >= C
    or (cleaner[0].x == x and cleaner[0].y == y) or (cleaner[1].x == x and cleaner[1].y == y);
}

void copy_copy_map(int copy_map[50][50]) {
    for(int i = 0; i < R; i++) {
        for(int j = 0; j < C; j++) {
            map[i][j] = copy_map[i][j];
        }
    }
}

void spread() {
    int copy_map[50][50] = {0,};
    for(int i = 0; i < R; i++) {
        for(int j = 0; j < C; j++) {
            if(map[i][j] <= 0) continue;
            int cnt = 0;
            for(int d = 0; d < 4; d++) {
                int nx = i+dx[d], ny = j+dy[d];
                if(can_not_spread(nx,ny)) continue;
                copy_map[nx][ny] += map[i][j]/5;
                cnt++;
            }
            copy_map[i][j] += map[i][j]-((map[i][j]/5)*cnt);
        }
    }
    copy_copy_map(copy_map);
}

void clean() {
    int sx = cleaner[0].x, sy = cleaner[0].y+1;
    int before = 0, after;
    // right
    while(sy < C) {
        after = map[sx][sy];
        map[sx][sy] = before;
        before = after;
        sy++;
    }
    sy--;
    // up
    sx--;
    while(sx >= 0) {
        after = map[sx][sy];
        map[sx][sy] = before;
        before = after;
        sx--;
    }
    sx++;
    // left
    sy--;
    while(sy >= 0) {
        after = map[sx][sy];
        map[sx][sy] = before;
        before = after;
        sy--;
    }
    sy++;
    // down
    sx++;
    while(sx < cleaner[0].x) {
        after = map[sx][sy];
        map[sx][sy] = before;
        before = after;
        sx++;
    }

    sx = cleaner[1].x; sy = cleaner[1].y+1;
    before = 0;
    // right
    while(sy < C) {
        after = map[sx][sy];
        map[sx][sy] = before;
        before = after;
        sy++;
    }
    sy--;
    // down
    sx++;
    while(sx < R) {
        after = map[sx][sy];
        map[sx][sy] = before;
        before = after;
        sx++;
    }
    sx--;
    // left
    sy--;
    while(sy >= 0) {
        after = map[sx][sy];
        map[sx][sy] = before;
        before = after;
        sy--;
    }
    sy++;
    // up
    sx--;
    while(sx > cleaner[1].x) {
        after = map[sx][sy];
        map[sx][sy] = before;
        before = after;
        sx--;
    }
}

void input() {
    cin >> R >> C >> T;
    int index = 0;
    for(int i = 0; i < R; i++) {
        for(int j = 0; j < C; j++) {
            cin >> map[i][j];
            if(map[i][j] == -1) {
                cleaner[index++] = {i,j};
            }
        }
    }
}

int count_dust() {
    int ret = 0;
    for(int i = 0; i < R; i++) {
        for(int j = 0; j < C; j++) {
            if(map[i][j] == -1) continue;
            ret += map[i][j];
        }
    }
    return ret;
}

int simulate() {
    for(int i = 0; i < T; i++) {
        spread();
        clean();
    }
    return count_dust();
}

int main() {
    input();
    cout << simulate() << '\n';

    return 0;
}