BOJ 17144 미세먼지 안녕

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

17144번: 미세먼지 안녕!

 

요즘은 시뮬레이션 문제 푸는게 재밌는 것 같다..

복잡한 알고리즘 고민없이 코딩할 수 있어서 그런가,,

 

마냥 구현만 하면 풀 수 있는 문제들이라 아무 생각없이 풀 수 있어 좋은 것 같다(생각없이 풀다보니 코드는 개판이 된다)

 

미세먼지 안녕! 문제는 1) 확산 2) 공기 순환을 구현하면 풀 수 있다.

확산에서 중요한 점은 확산 전 원본 배열을 기준으로 계산을 쭉 진행해야 하기 때문에, 새로운 배열이 필요하다.

나는 memcpy를 이용해 새로운 배열을 만들었고, O(n*2), n 이 1000 이하라 시간안에는 돌아가지만,

예전에 어떤 문제를 풀면서 memcpy가 상당히 느리다는 것을 알았다.. 직접 for문 돌린게 더 빨랐던 것 같기도

 

공기 순환은 rotate 라는 이름(함수 이름 짓기가 젤 어렵다)으로 구현했는데, 사실 실수가 많이 발생할 법한 구현이다.

left, right, up, down 으로 각각 쪼개서 구현해서, 시계방향은 down -> right -> up -> left 순서로 덮어써가고,
반시계방향은  up -> right -> down -> left 순서로 덮어써가면 실수를 줄일 수 있을 것 같다.

 

시뮬레이션 문제의 핵심은 구현 중 발생할 수 있는 실수를 최대한 줄이는게 핵심일 것 같다..

사실 좋은 코드는 실무에서 굉장히 중요하지만, 알고리즘을 풀면서 코드의 질이 크게 중요한 가 싶다 (변명 아님..)

 

 

소스코드

 

#include<stdio.h>
#include<string.h>
int arr[1111][1111], r,c,t;
int dy[4] = {-1,1,0,0}, dx[4] = {0,0,-1,1};
 
void rotate(int y, int x, int y_dir){
  arr[y+y_dir][x] = 0;
 
  for(int i=y+y_dir; i != (y_dir == -1 ? 0 : r-1); i += y_dir){
    arr[i][x] = arr[i+y_dir][x];
  }
 
  int y_ = y_dir == -1 ? 0 : r-1;
  for(int i=0; i<c-1; i++){
    arr[y_][i] = arr[y_][i+1];
  }
 
  for(int i=y_; i != y; i-= y_dir){
    arr[i][c-1] = arr[i-y_dir][c-1];
  }
 
  for(int i=c-1; i-1>0; i--){
    arr[y][i] = arr[y][i-1];
    arr[y][i-1] = 0;
  }
}
 
void spread(){
  int new_arr[1111][1111] = {0};
  memcpy(new_arr, arr, sizeof(arr));
  for(int i=0; i<r; i++){
    for(int j=0; j<c; j++){
      if(arr[i][j] >= 5){
        int cnt = 0;
        for(int d=0; d<4;d++){
          int ny = i+dy[d], nx = j+dx[d];
          if(ny>=0 && ny< r&& nx>=0 && nx< c && arr[ny][nx] != -1){
            cnt+=1;
            new_arr[ny][nx] += arr[i][j]/5;
          }
        }
        new_arr[i][j] -= arr[i][j]/5 * cnt;
      }
    }
  }
  memcpy(arr, new_arr, sizeof(arr));
}
int main(){
  int src_y = -1;
  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][0] == -1 && src_y == -1)
      src_y = i;
  }
 
  for(int i=0; i<t; i++){
    spread();
    rotate(src_y, 0, -1);
    rotate(src_y+1, 0, 1);
  }
  int ans= 0;
  for(int i=0;i<r;i++){
    for(int j=0; j<c;j++){
      ans += arr[i][j];
    }
  }
 
  printf("%d\n", ans+2);
  return 0;
}