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

 

 구현 문제다. 크게 복잡하거나 어려운 부분은 없는데, 오히려 메모리 아끼겠답시고 포인터를 이용하다가 for문 안에서 선언해 둔 로컬 레퍼런스를 그대로 이용해서 갱신하는 바람에 문제가 좀 생겼다.

 for문 안에서 일반 vector타입으로 선언해도 힙 영역에 할당된 메모리 공간은 따로 릴리즈 해주지 않는 이상 계속 살아있을 줄 알았는데, 디버깅하면서 메모리 공간을 보니까 vector 레퍼런스가 날아가면서 힙 영역도 같이 릴리즈 되는 것 같았다.

 그래서 그 임시 vector를 for문 밖으로 빼버리고 아예 그쪽도 포인터로 선언해서 new로 직접 메모리를 할당해줬더니 문제없이 돌아갔다.

 

 문제에 대한 로직은 나와있는 그대로 구현했다. R과 C의 크기가 최대 50이고, T도 최대 1,000이기 때문에 매 초마다 모든 행렬을 확인해 줘도 시간 복잡도 문제가 발생하지 않는다. C++과 같은 언어를 사용했다면, 잘못된 배열 인덱스에 접근하는 것만 주의해 주고 무난하게 해결할 수 있다.

 

#include <iostream>
#include <vector>

using namespace std;

int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};

int main() {
    int r, c, t;
    cin >> r >> c >> t;

    vector<vector<int> >* matrix = new vector<vector<int> >(r, vector<int>(c, 0));
    pair<int, int> cleanerPosition; // {r, c}

    for(int i=0; i<r; i++) {
        for(int j=0; j<c; j++) {
            cin >> (*matrix)[i][j];
            if((*matrix)[i][j]==-1) {
                cleanerPosition = {i, j};
            }
        }
    }

    vector<vector<int> >* newMatrix;
    for(int time=0; time<t; time++) {
        //미세먼지 확산
        newMatrix = new vector<vector<int> >(r, vector<int>(c, 0));
        for(int i=0; i<r; i++) {
            for(int j=0; j<c; j++) {
                int cnt = 0;
                if((*matrix)[i][j]>0) {
                    for(int k=0; k<4; k++) {
                        int adjR = i+dy[k];
                        int adjC = j+dx[k];
                        if(adjR>=0 && adjR<r && adjC>=0 && adjC<c && (*matrix)[adjR][adjC]!=-1) {
                            (*newMatrix)[adjR][adjC] += (*matrix)[i][j] / 5;
                            cnt++;
                        }
                    }
                    (*newMatrix)[i][j] += (*matrix)[i][j] - ((*matrix)[i][j]/5*cnt);
                } else {
                    (*newMatrix)[i][j] += (*matrix)[i][j];
                }
            }
        }

        //공기 청정기
        //위쪽
        int posY = cleanerPosition.first-2;
        int posX = cleanerPosition.second;

        while(posY>0) { 
            (*newMatrix)[posY][posX] = (*newMatrix)[posY-1][posX];
            posY--;
        }
        while(posX<c-1) {
            (*newMatrix)[posY][posX] = (*newMatrix)[posY][posX+1];
            posX++;
        }
        while(posY<cleanerPosition.first-1) {
            (*newMatrix)[posY][posX] = (*newMatrix)[posY+1][posX];
            posY++;
        }
        while(posX>1) {
            (*newMatrix)[posY][posX] = (*newMatrix)[posY][posX-1];
            posX--;
        }
        (*newMatrix)[posY][posX] = 0;

        //아래쪽        
        posY = cleanerPosition.first+1;
        posX = cleanerPosition.second;
        while(posY<r-1) {
            (*newMatrix)[posY][posX] = (*newMatrix)[posY+1][posX];
            posY++;
        }
        while(posX<c-1) {
            (*newMatrix)[posY][posX] = (*newMatrix)[posY][posX+1];
            posX++;
        }        
        while(posY>cleanerPosition.first) {
            (*newMatrix)[posY][posX] = (*newMatrix)[posY-1][posX];
            posY--;
        }
        while(posX>1) {
            (*newMatrix)[posY][posX] = (*newMatrix)[posY][posX-1];
            posX--;
        }
        (*newMatrix)[posY][posX] = 0;

        delete matrix;
        matrix = newMatrix;
    }

    int sum = 0;
    for(int i=0; i<r; i++) {
        for(int j=0; j<c; j++) {
            if((*matrix)[i][j]>0) {
                sum += (*matrix)[i][j];
            }
        }
    } 
    cout << sum;   
}