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

 

17144번: 미세먼지 안녕!

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사

www.acmicpc.net

 

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

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

 

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

 

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

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

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

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

 

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

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

 

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

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

 

 

소스코드

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. int arr[1111][1111], r,c,t;
  4. int dy[4] = {-1,1,0,0}, dx[4] = {0,0,-1,1};
  5.  
  6. void rotate(int y, int x, int y_dir){
  7. arr[y+y_dir][x] = 0;
  8.  
  9. for(int i=y+y_dir; i != (y_dir == -1 ? 0 : r-1); i += y_dir){
  10. arr[i][x] = arr[i+y_dir][x];
  11. }
  12.  
  13. int y_ = y_dir == -1 ? 0 : r-1;
  14. for(int i=0; i<c-1; i++){
  15. arr[y_][i] = arr[y_][i+1];
  16. }
  17.  
  18. for(int i=y_; i != y; i-= y_dir){
  19. arr[i][c-1] = arr[i-y_dir][c-1];
  20. }
  21.  
  22. for(int i=c-1; i-1>0; i--){
  23. arr[y][i] = arr[y][i-1];
  24. arr[y][i-1] = 0;
  25. }
  26. }
  27.  
  28. void spread(){
  29. int new_arr[1111][1111] = {0};
  30. memcpy(new_arr, arr, sizeof(arr));
  31. for(int i=0; i<r; i++){
  32. for(int j=0; j<c; j++){
  33. if(arr[i][j] >= 5){
  34. int cnt = 0;
  35. for(int d=0; d<4;d++){
  36. int ny = i+dy[d], nx = j+dx[d];
  37. if(ny>=0 && ny< r&& nx>=0 && nx< c && arr[ny][nx] != -1){
  38. cnt+=1;
  39. new_arr[ny][nx] += arr[i][j]/5;
  40. }
  41. }
  42. new_arr[i][j] -= arr[i][j]/5 * cnt;
  43. }
  44. }
  45. }
  46. memcpy(arr, new_arr, sizeof(arr));
  47. }
  48. int main(){
  49. int src_y = -1;
  50. scanf("%d%d%d", &r,&c,&t);
  51.  
  52. for(int i=0;i<r;i++){
  53. for(int j=0; j<c; j++){
  54. scanf("%d", &arr[i][j]);
  55. }
  56. if(arr[i][0] == -1 && src_y == -1)
  57. src_y = i;
  58. }
  59.  
  60. for(int i=0; i<t; i++){
  61. spread();
  62. rotate(src_y, 0, -1);
  63. rotate(src_y+1, 0, 1);
  64. }
  65. int ans= 0;
  66. for(int i=0;i<r;i++){
  67. for(int j=0; j<c;j++){
  68. ans += arr[i][j];
  69. }
  70. }
  71.  
  72. printf("%d\n", ans+2);
  73. return 0;
  74. }
  75.  

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 17144 미세먼지 안녕  (0) 2021.06.27
BOJ 14891 톱니바퀴  (0) 2021.06.12
BOJ 14503 로봇 청소기  (0) 2021.06.12
BOJ 1969 DNA  (0) 2021.05.24
BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24

+ Recent posts