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

문제 링크: https://www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

<문제풀이> 시뮬레이션, BFS

 

미세먼지 확산은 BFS를 사용하면 됩니다. 그런데 확산할 때 주의할 점은 모든 미세먼지는 동시에 확산이 되기 때문에 BFS로 미세먼지를 하나하나 가져올 때마다 확산될 미세먼지의 양을 원본 배열에서 계산하면 안 되고 확산되기 전에 상태를 임시로 저장한 temp 배열에서 계산해야 합니다. (BFS는 하나씩 순서대로 처리하므로 하나 처리할 때마다 배열의 값이 바뀌기 때문에 다른 값에 영향을 주게 됩니다.)

 

공기청정기는 2차원 배열의 특정 행, 열을 기준으로 위, 아래, 왼쪽, 오른쪽 방향으로 한 칸씩 원소를 이동시키는 걸 구현하고

각 공기청정기를 기준으로 위쪽 공기청정기는 down, left, up, right 순서대로 원소를 이동시키면 되고, 아래쪽 공기청정기는 up, left down, right 순서대로 원소를 이동시키면 됩니다.  

 

<C++ 소스 코드>

#include<iostream>
#include<queue>
#include<utility>
using namespace std;
 
#define X first
#define Y second
 
const int dx[4] = { 0, 0, 1 ,-1 };
const int dy[4] = { 1, -1, 0, 0 };
int R, C, T;
int A[1000][1000];
int temp[1000][1000]; //미세먼지 확산을 위한 A의 데이터 임시 저장
int xAir1; //위쪽 공기청정기
int xAir2; //아래쪽 공기청정기
 
//x행의 a ~ b 원소를 왼쪽으로 한 칸씩 이동
void left(int x, int a, int b) {
    for (int y = a; y <= b; y++) {
        A[x][y - 1] = A[x][y];
        A[x][y] = 0;
    }
}
//x행의 a ~ b 원소를 오른쪽으로 한 칸씩 이동
void right(int x, int a, int b) {
    for (int y = b; y >= a; y--) {
        A[x][y + 1] = A[x][y];
        A[x][y] = 0;
    }
}
//y열의 a ~ b 원소를 위쪽으로 한 칸씩 이동
void up(int y, int a, int b) {
    for (int x = a; x <= b; x++) {
        A[x - 1][y] = (A[x-1][y] == -1) ? -1 : A[x][y];
        A[x][y] = 0;
    }
}
 
//y열의 a ~ b 원소를 아래쪽으로 한 칸씩 이동
void down(int y, int a, int b) {
    for (int x = b; x >= a; x--) {
        A[x + 1][y] = (A[x + 1][y] == -1) ? -1 : A[x][y];
        A[x][y] = 0;
    }
}
 
//미세먼지 확산
void bfs() {
    queue<pair<int, int > > Q;
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (A[i][j] == -1 || A[i][j] == 0) continue;
            Q.push({ i, j });
        }
    }
 
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if(nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
            if (A[nx][ny] == -1) continue;
    
            A[nx][ny] += temp[cur.X][cur.Y] / 5;
            A[cur.X][cur.Y] -= temp[cur.X][cur.Y] / 5;
        }
    }
}
//공기청정기 작동
void runAir() {
    //위쪽 공기청정기
    down(0, 0, xAir1 - 1);
    left(0, 1, C - 1);
    up(C - 1, 1, xAir1);
    right(xAir1, 1, C-2);
    
    //아래쪽 공기청정기
    up(0, xAir2  +1, R  -1);
    left(R-1, 1, C-1);
    down(C-1, xAir2, R -2);
    right(xAir2, 1, C-2);
}
 
 
//미세먼지 확산을 위한 temp 배열 초기화
void init() {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            temp[i][j] = A[i][j];
        }
    }
}
 
int solution() {
    int res = 0;
    for (int t = 0; t < T; t++) {
        init();
        bfs();
        runAir();
 
    }
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (A[i][j] == -1) continue;
            res += A[i][j];
        }
    }
    return res;
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> R >> C >> T;
 
    int cnt = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> A[i][j];
            if (A[i][j] == -1 && cnt == 0) {
                xAir1 = i; 
                cnt++;
            }
            else if (A[i][j] == -1 && cnt == 1) {
                xAir2 = i;
                cnt++;
            }
            
        }
    }
 
    cout<< solution();
    return 0;
}