BOJ 17144 : 미세먼지 안녕! [C++]

 

17144번: 미세먼지 안녕!

 

미세먼지 확산 과정을 이해하지 못한 점과 DFS + 시뮬레이션이라 생각한 것 때문에 푸는데 오래 걸렸다.

어찌어찌 DFS + 시뮬레이션을 통해 아주 느린 속도로 통과를 한 후,

다른 블로그를 찾아보니 단순 구현 + 시뮬레이션이었고, 문제 분류도 그랬다.

 

 

 

미세먼지 확산은 모두 "동시"에 일어난다.

이를 구현하기 위해 각 칸이 받는 영향(먼지를 퍼트려 먼지가 줄어들거나, 옆 칸의 먼지가 확산되어 먼지가 늘어나거나)을

기록할 배열이 따로 있어야 한다.

각 칸의 증감량을 모두 기록한 후, 이를 각 칸에 더해주면 동시에 확산되는 것을 코드로 표현할 수 있다.

 

공기청정기에 의해 먼지가 이동하는 과정은 위쪽과 아래쪽 각각 for문 4개씩 사용하여 구현했다.

 

밑에 첨부된 코드는 기존의 통과 코드를 다른 블로그 글을 보고 고친 코드이다.

 

코드

#include <iostream>

int r;
int c;
int t;
int head_row = 0;
int tail_row;
int room[50][50];
int tmp[50][50];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void init() {
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            tmp[i][j] = 0;
        }
    }
}

void spread() {
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (room[i][j] > 0) {
                int cnt = 0;
                for (int k = 0; k < 4; k++) {
                    int ni = i + dx[k];
                    int nj = j + dy[k];

                    if (ni < 0 || ni > r - 1 || nj < 0 || nj > c - 1) {
                        continue;
                    }

                    if (room[ni][nj] == -1) {
                        continue;
                    }

                    tmp[ni][nj] += room[i][j] / 5;
                    cnt++;
                }
                tmp[i][j] -= (room[i][j] / 5) * cnt;
            }
        }
    }
}

void circulate_head() {
    for (int i = head_row - 1; i > 0; i--) {
        room[i][0] = room[i - 1][0];
    }
    for (int i = 0; i < c - 1; i++) {
        room[0][i] = room[0][i + 1];
    }
    for (int i = 0; i < head_row; i++) {
        room[i][c - 1] = room[i + 1][c - 1];
    }
    for (int i = c - 1; i > 0; i--) {
        if (i == 1) {
            room[head_row][i] = 0;
        } else {
            room[head_row][i] = room[head_row][i - 1];
        }
    }
}

void circulate_tail() {
    for (int i = tail_row + 1; i < r - 1; i++) {
        room[i][0] = room[i + 1][0];
    }
    for (int i = 0; i < c - 1; i++) {
        room[r - 1][i] = room[r - 1][i + 1];
    }
    for (int i = r - 1; i > tail_row; i--) {
        room[i][c - 1] = room[i - 1][c - 1];
    }
    for (int i = c - 1; i > 0; i--) {
        if (i == 1) {
            room[tail_row][i] = 0;
        } else {
            room[tail_row][i] = room[tail_row][i - 1];
        }
    }
}

void sol() {
    for (int tt = 0; tt < t; tt++) {
        init();
        spread();

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                room[i][j] += tmp[i][j];
            }
        }

        circulate_head();
        circulate_tail();
    }
}

int main()
{
    std::cin >> r >> c >> t;

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            std::cin >> room[i][j];
            if (room[i][j] == -1) {
                if (head_row == 0) {
                    head_row = i;
                } else {
                    tail_row = i;
                }
            }
        }
    }

    sol();

    int ans = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (room[i][j] > 0) {
                ans += room[i][j];
            }
        }
    }

    std::cout << ans << "\n";

    return 0;
}