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

망할 미세먼지 때문에 내 차가 세차를 해도 일주일을 못가는거 같다...ㅂㄷㅂㄷ

일단 망할 미세먼지가 퍼지는건 구현하기 위해서도 구조체 배열로 저장하는게 좋기도 하고... 좀 비효율적인거 같기도 하고

일단 이 문제는 공기청정기를 돌리는 과정에서 너무 구현하기 귀찮아서 한 10번은 코드짜다 지웠다 한거같다

어떻게든 덜 귀찮게 짜려고...그래도 일단은 일전에 풀었던 블록게임에서 아이디어를 얻었다...

DFS로 좌표 끝까지 가고 돌아오면서 갱신하는 방법을 사용

1. 먼저 먼지가 퍼질 수 있는 조건 map[i][j] / 5가 1이상인 지점을 구조체 배열을 만들어 좌표와 그 값을 저장

2. 미세먼지가 저장된 구조체 배열에서 하나씩 꺼내어 4방향 검사하는데, 이때 먼지가 못퍼지는 경우(공기청정기 or 배열 범위 초과)는 퍼트리지 않는다

- 구조체 배열에 저장하는 이유는 바로 map에서 퍼트릴 경우엔 다음 퍼트릴 먼지에 영향이 갈 것이라고 생각했기 때문이다.

- 낚시왕처럼 tmp배열을 만들고도 싶었으나 시간이 굉장히 길어지면...시간 복잡도가 엄청 뛸 것이라고 생각함

3. 이렇게 먼지를 한번 퍼트리고 나면 이제 공기청정기를 돌려주기 위해 재귀함수로 한바퀴 돌려준다

- 방향 전환이 필요할 경우에는 다른 방법이 있을 수 있겠으나, 2칸의 공기청정기를 따로 돌려주기 때문에 그냥 좌표와 조건에 따라 임의로 방향을 바꿔줌

4. 좌표 끝까지 도달했다면, 리턴하며 map의 값을 바꿔준다

- 이때, 맨끝점을 제외하고는 현재 map의 값을 따로 저장하고, 갱신 후 저장된 값을 리턴해야한다

5. 이 순서로 T번 반복하고 그냥 for문으로 map을 전부 순회하며 먼지들을 다 더하고 출력은 +2를 한다

- 공기청정기 -1이 두개 있기 때문

#include <iostream>
#define MAXSIZE 52
using namespace std;
 
struct AIR {
    int x, y, dust;
}air[2], dust_[MAXSIZE*MAXSIZE];
 
int map[MAXSIZE][MAXSIZE];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
int N, M, T, dab;
 
int dfs(int d, int x, int y, int dir, int air_num) {
    if (d != 0 && map[y][x] == -1) return 0;
    if (air_num == 0) {
        if (y == 0 && dir == 0) { dir = 3; }
        else if (x == M - 1 && dir == 3) { dir = 1; }
        else if (y == air[air_num].y && dir == 1) { dir = 2; }
    }
    if (air_num == 1) {
        if (y == N - 1 && dir == 1) { dir = 3; }
        else if (x == M - 1 && dir == 3) { dir = 0; }
        else if (y == air[air_num].y && dir == 0) { dir = 2; }
    }
    int nx = x + dx[dir], ny = y + dy[dir];
    int ret = map[y][x];
    map[y][x] = dfs(d + 1, nx, ny, dir, air_num);
    return ret;
}
 
int main(void) {
    cin >> N >> M >> T;
    int air_cnt = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
            if (map[i][j] == -1) { air[air_cnt].x = j; air[air_cnt].y = i; air_cnt++; }
        }
    }
    for (int t = 1; t <= T; t++) {
    
        int dust_cnt = 0;
        for (int i = 0; i < N; i++) { // 뿌려질 먼지가 있는 곳을 search
            for (int j = 0; j < M; j++) {
                if (map[i][j] && (map[i][j] / 5 >= 1)) {
                    dust_[dust_cnt].x = j; dust_[dust_cnt].y = i; dust_[dust_cnt].dust = map[i][j]; dust_cnt++;
                }
            }
        }
 
        for (int i = 0; i < dust_cnt; i++) { //먼지 퍼트리기
            int ix = dust_[i].x, iy = dust_[i].y, d_dust = dust_[i].dust / 5;
            for (int d = 0; d < 4; d++) {
                int nx = ix + dx[d], ny = iy + dy[d];
                if (nx < 0 || ny < 0 || nx >= M || ny >= N || map[ny][nx] == -1) continue;
                map[ny][nx] += d_dust;    map[iy][ix] -= d_dust;
            }
        }
        map[air[0].y][air[0].x] = dfs(0, air[0].x, air[0].y, 0, 0);
        map[air[1].y][air[1].x] = dfs(0, air[1].x, air[1].y, 1, 1);
    }
    for (int y = 0; y < N; y++)
        for (int x = 0; x < M; x++)
            dab += map[y][x];
    cout << dab + 2 << endl;
    return 0;
}