[백준] 미세먼지 안녕! 17144번 (c++) 구현, 로컬 배열 선언의 중요, 탐색 순서의 중요

출처 : https://www.acmicpc.net/problem/17144

 

풀이 방법

문제의 핵심

1. 미세 먼지는 동시에 전파된다.
   1. 임시 배열을 사용해서 한 번에 업데이트하면 된다.
   2. 임시 배열을 로컬 변수로 선언했다. 
      1. 로컬 배열은 항상 memset으로 초기화 해야한다.
2. 공기 청정기의 미세먼지 밀어내기 구현
   1. 코너 부분에서 간단하게 구현하기 위해 밀어내기를 구현하는 순서가 중요하다.
   2. 윗부분 같은 경우 왼쪽, 밑, 오른쪽, 위 쪽 순서로 밀어낸다면 코너 부분에 크게 신경 쓰지 않아도 된다.
3. 공기 청정기 위 아래 구하기
   1. 두 입력을 받고 정렬을 통해 위 아래 구분이 가능하다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>

using namespace std;

int R, C, T;
int room[51][51];
vector<int> machine;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

void air_clear() {
    //위쪽 반시계 방향
    //왼, //위, //오, //밑
    // 1. 왼쪽줄
    for (int i = machine[0]-1;i > 0;i--) { 
        room[i][0] = room[i-1][0];
    }
    // 2. 위쪽줄
    for (int i = 0;i < C-1; i++) { 
        room[0][i] = room[0][i+1];
    }
    // 3. 오른쪽줄
    for (int i = 1;i <= machine[0];i++) { 
        room[i-1][C-1] = room[i][C-1];
    }
    // 4.아랫줄
    for (int i = C-1;i > 1;i--) { 
        room[machine[0]][i] = room[machine[0]][i-1];
    }
    room[machine[0]][1] = 0;

    //아래쪽 시계 방향
    //왼, // 밑, //오, // 위

    // 아래공기 순환 (시계)
    // 1. 왼쪽줄
    for (int i = machine[1] + 1; i < R - 1; i++)
        room[i][0] = room[i + 1][0];
    // 2. 아랫줄
    for (int i = 0; i < C - 1; i++)
        room[R - 1][i] = room[R - 1][i + 1];
    // 3. 오른쪽줄
    for (int i = R - 1; i >= machine[1]; i--)
        room[i][C - 1] = room[i - 1][C - 1];
    // 4. 윗줄
    for (int i = C - 1; i > 1; i--)
        room[machine[1]][i] = room[machine[1]][i - 1];
    room[machine[1]][1] = 0;
}

void spread() {
    int temp[51][51]; //전파를 위한 임시 배열
    memset(temp, 0, sizeof(temp));
    for (int i = 0;i < R;i++) {
        for (int j = 0;j < C;j++) {

            if (room[i][j] < 1) continue; // 비었거나, 청정기일 때 패스하기

            int cnt = 0, val = room[i][j] / 5; // 전파 값

            for (int k = 0;k < 4;k++) { // 동서남북 전파하기
                int ny = i + dy[k];
                int nx = j + dx[k];
                if (ny >= 0 && ny < R && nx >= 0 && nx < C) {
                    if (room[ny][nx] != -1) {
                        temp[ny][nx] += val;
                        cnt++;
                    }
                }
            }
            temp[i][j] -= (val * cnt); // 전파 횟수만큼 빼주기
        }
    }

    for (int i = 0;i < R;i++) { // 전파 결과 업데이트
        for (int j = 0;j < C;j++) {
            room[i][j] += temp[i][j];
            temp[i][j] = 0;
        }
    }

}

int main() {
    cin >> R >> C >> T;

    for (int i = 0;i < R;i++) { // 방 입력 받기
        for (int j = 0;j < C;j++) {
            cin >> room[i][j];
            if (room[i][j] == -1) { // 청정기이면 벡터에 저장
                machine.push_back(i);
            }
        }
    }
    sort(machine.begin(), machine.end()); // 정렬을 통해 청정기의 위아래 구분

    for (int i = 0;i < T;i++) { // T초 통안 저파
        spread();
        air_clear();
    }
    int ans = 0;
    for (int i = 0;i < R;i++) { // T초 후 미세먼지 카운트
        for (int j = 0; j < C;j++) {
            if (room[i][j] > 0) {
                ans += room[i][j];
            }
        }
    }
    cout << ans << endl;
    return 0;
}