1) 문제 분석
1초 마다 모든 칸을 갱신해주어야 한다:
- 각 칸에서 확산되는 미세먼지 양 계산
- 각 칸에서 확산된 미세먼지 양은 빼고, 다른 칸에서 확산되어온 미세먼지 양을 더함
- 공기청정기 바람대로 미세먼지 한 칸씩 이동
- 위 과정을 T초 동안 반복
처음에는 bfs 등을 이용하는 그래프 문제인가 싶었는데 그 방법이 더 시간이 많이 걸리고 복잡할 것 같아서 문제에서 요구하는 그대로 코드를 작성해보았다.
2) 알고리즘
- 우선 pos 라는 struct 타입을 정의한다.
~~~ typedef struct _pos{ int value; int modified; }pos;
~~~
value에는 그 칸의 미세먼지 값이, modified에는 다른 칸에서 유입되는 미세먼지양과 이 칸에서 다른 칸으로 빠져나가는 총 미세먼지 양의 합이 저장된다. 입력을 받을 때, 각 칸의 value 값은 입력대로, modified 값은 0으로 초기화 해준다.
-
각 칸을 돌면서, 우선 인접한 칸들로 확산되는 미세먼지 양을 구해서 diffuse 변수에 저장한다. 그리고 현재 칸의 상하좌우 위치한 칸이 있는지 확인하고, 공기청정기가 있는 칸이 아니라면 그 diffuse 값을 인접 칸의 modified 값에 누적시켜준다. count 변수를 사용하여, 미세먼지가 확산되는 인접 칸의 개수를 기억하고, 그 횟수*diffuse 값 만큼을 현재 칸의 modified 값에서 빼준다.
-
처음부터 칸을 돌면서 현재 값에 modified 값을 더해 새로운 미세먼지 양을 구해준다. 이 작업이 끝나면, 공기청정기의 바람에 따라 미세먼지 값을 이동시킨다. 이 작업은 그냥 루프 돌려가면서 일일히 코딩해주었다. 이런식으로 총 T번을 반복한다.
-
T번 반복이 끝나면 다시 한 번 처음부터 칸을 돌면서 value 값을 더해주면 총 미세먼지 양의 값을 구할 수 있다.
놀랍게도 한 번에 성공했다!
3) 코드
#include <iostream>
using namespace std;
typedef struct _pos{
int value;
int modified;
}pos;
int R, C, T; //R: row, C: column, T: T times
int air_x, air_y; //coordinates of air cleaner
pos** board;
int main(){
int n;
//get input from user
cin >> R;
cin >> C;
cin >> T;
board = new pos*[R];
for(int i=0; i<R; i++)
board[i] = new pos[C];
//initialize values
for(int i=0; i<R; i++){
for(int j=0; j<C; j++){
cin >> n;
board[i][j].value = n;
board[i][j].modified = 0;
//location of air cleaner
if(n==-1){
air_x = i; air_y = j;
}
}
}
for(int t=0; t<T; t++) {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
//calculate the amount diffused
int diffuse = board[i][j].value / 5;
int count = 0;
//flow of dust from current block to adjacent blocks
//upwards
if (i - 1 >= 0 && board[i - 1][j].value != -1) {
board[i - 1][j].modified += diffuse;
count++;
}
//leftwards
if(j-1 >= 0 && board[i][j-1].value != -1) {
board[i][j-1].modified += diffuse;
count++;
}
//downwards
if(i+1<R && board[i+1][j].value != -1 ){
board[i+1][j].modified += diffuse;
count++;
}
//rightwards
if(j+1<C && board[i][j+1].value != -1){
board[i][j+1].modified += diffuse;
count++;
}
//calculate total amount of in&out
board[i][j].modified -= count*diffuse;
}
}
//calculate new amount
for(int i=0; i<R; i++){
for(int j=0; j<C; j++){
board[i][j].value += board[i][j].modified;
board[i][j].modified = 0;
}
}
//flow of air (upper)
//downwards
for(int k=air_x-2; k>0; k--)
board[k][0] = board[k-1][0];
//rightwards
for(int k=1; k<C; k++)
board[0][k-1] = board[0][k];
//upwards
for(int k=1; k<=air_x-1; k++)
board[k-1][C-1] = board[k][C-1];
//leftwards
for(int k=C-2; k>=1; k--)
board[air_x-1][k+1] = board[air_x-1][k];
board[air_x-1][1].value = 0;
//flow of air (lower)
//upwards
for(int k=air_x+1; k<R-1; k++)
board[k][0] = board[k+1][0];
//leftwards
for(int k=1; k<C; k++)
board[R-1][k-1] = board[R-1][k];
//downwards
for(int k=R-1; k>air_x; k--)
board[k][C-1] = board[k-1][C-1];
//rightwards
for(int k=C-1; k>1; k--)
board[air_x][k] = board[air_x][k-1];
board[air_x][1].value = 0;
}
//calculate the final value
int total = 0;
for(int i=0; i<R; i++){
for(int j=0; j<C; j++){
if(board[i][j].value != -1)
total += board[i][j].value;
}
}
//print out answer
cout<<total;
}