#문제
17144번: 미세먼지 안녕!
https://www.acmicpc.net/problem/17144
17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사
www.acmicpc.net
#접근방법
구현, 시뮬레이션 문제이다. 문제에서 제시한 대로 코드를 작성해주면 된다.
#풀이
#include <stdio.h>
#include <memory.h>
int arr[55][55];
int temp[55][55];
int xx[4] = {-1,0,1,0};
int yy[4] = {0,1,0,-1};
int main(){
int r,c,t;
int air;
int ans=0;
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) air = i;
}
while(t--){
//미세먼지확산
for(int i=0;i<r;i++)
memset(temp[i],0,c*sizeof(int));
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
if(arr[i][j]>0){
int cnt = 0;
for(int k=0;k<4;k++){
int x = i+xx[k];
int y = j+yy[k];
if(x>=0 && x<r && y>=0 && y<c && arr[x][y]!=-1){
temp[x][y] += arr[i][j]/5;
cnt++;
}
}
arr[i][j] -= arr[i][j]/5*cnt;
}
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
arr[i][j] += temp[i][j];
//반시계방향
int x = air-2;
int y = 0;
int prex = air-3;
int prey = 0;
int direction = 0;
while(arr[prex][prey]!=-1){
arr[x][y] = arr[prex][prey];
x = prex;
y = prey;
if(prex+xx[direction]<0 || prex+xx[direction]>=air || prey+yy[direction]<0 || prey+yy[direction]>=c)
direction = (direction+1)%4;
prex += xx[direction];
prey += yy[direction];
}
arr[x][y] = 0;
//시계방향
x = air+1;
y = 0;
prex = air+2;
prey = 0;
direction = 2;
while(arr[prex][prey]!=-1){
arr[x][y] = arr[prex][prey];
x = prex;
y = prey;
if(prex+xx[direction]<air || prex+xx[direction]>=r || prey+yy[direction]<0 || prey+yy[direction]>=c)
direction = (direction+3)%4;
prex += xx[direction];
prey += yy[direction];
}
arr[x][y] = 0;
}
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
ans += arr[i][j];
ans += 2;
printf("%d",ans);
return 0;
}
r,c,t를 입력받고 arr배열에 미세먼지를 저장시켜준다. 그리고 air 변수에 공기청정기의 아래 위치를 저장한다.
이 문제는 구현과 시뮬레이션 문제이므로 문제에서 제시한 순서대로 코드를 작성해 주면 된다.
먼저 미세먼지의 확산이 되고 그 다음 공기청정기가 작동이 된다.
반복문을 통해 arr배열에 미세먼지가 있을 경우, temp배열의 상 하 좌 우에 arr[i][j]/5를 더해준다.
memset함수로 temp배열을 0으로 초기화 시켜준다.
미세먼지 확산 값을 temp배열에 저장시켜 주는 이유는 arr배열에 바로 더하는 것을 적용할 경우, 다음 arr[i][j]/5 배열에 확산된 미세먼지를 한번 더 확산하게 되므로 temp 배열에 확산한 값을 저장하고 나중에 arr배열에 temp값을 더해주어서 이중 확산을 방지한다.
미세먼지가 확산이 된 후, 공기청정기가 작동이 되는데 공기청정기 위쪽 부분은 반시계 방향으로 공기가 순환이 되고, 아래 부분은 시계 방향으로 순환이 된다.
먼저 위쪽부분 반시계 방향으로 순환시켜 주었다.
x,y 변수는 순환된 공기가 이동하는 위치, prex, prey는 순환될 공기의 위치이다.
arr[x][y] = arr[prex][prey]로 prex,prey에 위치하는 공기를 x,y로 옮겨준다.
direction은 상 하 좌 우 중에 하나를 나타내는 변수이다.
0,1,2,3 순서대로 상, 하, 좌, 우를 뜻한다.
xx와 yy배열으로 방향벡터를 만들어 prex += xx[direction], prey += yy[direction]으로 순환되는 공기의 위치를 설정하였다.
만약 순환되는 위치의 범위를 벗어난다면 조건문을 통하여 direction = (direction+1)%4으로 방향을 바꿔주었다.
그다음 아래부분 시계 방향 순환도 반시계랑 코드가 거의 유사하다.
direction의 초기값이 2인 것, 벗어나는 위치가 다른 것, 그리고 direction = (direction+3)%4으로 역방향으로 설정한 것이 다른점이다.
위 코드를 t초 만큼 반복하고 공기청정기 위치를 제외한 나머지 arr배열에 있는 미세먼지 값들을 더해 출력하면 정답이다.
#성능
#정리
문제에서 제시한대로 구현할 수 있는 구현력,
시뮬레이션을 할 때 예외처리를 잘 해준다면 풀 수 있는 문제였다.
'하루 한 문제' 카테고리의 다른 글
[백준] 11723번 : 집합 [C/C++] (0) | 2022.06.18 |
---|---|
[백준] 1676번 : 팩토리얼 0의 개수 [C/C++] (0) | 2022.06.17 |
[백준] 14938번 : 서강그라운드 [C/C++] (0) | 2022.05.27 |
[백준] 11404번 : 플로이드 [C/C++] (0) | 2022.04.12 |
[백준] 1967번 : 트리의 지름 [C/C++] (0) | 2022.04.10 |