[ BOJ - 17144번 ] 미세먼지 안녕! (C++)

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

 

 R, C는 최대 50, T는 최대 1000이므로,

RxC 크기의 2차원 배열을 T번 탐색하는데 필요한 연산 횟수가 매우 작고 vector의 random access의 시간복잡도는 O(1)이므로, 시간복잡도를 줄이기 위한 방법을 생각할 필요 없이 2차원 벡터를 이용해 확산과 공기청정 기능을 구현하여 문제를 해결항 수 있을 것이라고 생각했다.

 

[ 풀이 방법 ]

1. 미세먼지 확산 기능

  - 2차원 배열의 모든 칸 돌면서 상하좌우로 확산

  - 확산은 모든 미세먼지에서 모든 방향으로 동시에  발생해야 한다.

  (배열을 2개(ORIGIN, AUX) 사용하여 확산 일어나기 전과 후의 상황을 저장하여 확산이 일어나는 순서에 영향 받지 않도록 구현)

 

2. 공기청정기 작동 기능

  - 공기청정기의 위치를 위, 아래로 나누어 저장

  - 공기청정 기능

    - 공기청정기의 위쪽 칸: 시작 위치 기준으로 오른쪽 끝 => 위쪽 끝 => 왼쪽 끝 => 아래쪽(공기청정기의 위쪽 칸 까지)으로 순환

    - 공기청정기의 아래쪽 칸: 시작 위치 기준으로 오른쪽 끝 => 아래쪽 끝 => 왼쪽 끝 => 위쪽(공기청정기의 아래쪽 칸 까지)으로 순환

  

위의 기능을 T번 반복한 뒤 남아있는 미세먼지의 양을 출력하여 문제를 해결하였다.

 

 공기청정 기능을 하드코딩하여 구현 중간에 실수 있었으나, 풀이 방법을 정리하고 구현했기 때문에 어디서 실수가 일어났을지 쉽게 찾을 수 있었고 디버깅하여 정답을 맞출 수 있었다.

 

[ 정답 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int R, C, T;
vector<vector<int>> map;

int upX; int upY;
int downX; int downY;

int dirX[4] = {-1, 0, 1, 0};
int dirY[4] = {0, -1, 0, 1};

void spread() {
    vector<vector<int>> aux(R, vector<int>(C));
    
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            
            if(map[i][j]) {
                
                int sum = 0;
                int quantity = map[i][j]/5;
                
                for (int dir = 0; dir < 4; dir++) {
                    int nx = i + dirX[dir];
                    int ny = j + dirY[dir];
                    
                    if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
                    if(nx == upX && ny == upY) continue;
                    if(nx == downX && ny == downY) continue;
                    
                    aux[nx][ny] += quantity;
                    sum += quantity;
                }
                
                aux[i][j] += map[i][j] - sum;
            }
        }
    }
    aux.swap(map);
    aux.clear();
}

void clean() {
    
    int prev = map[upX][upY];
    for (int i = 1; i < C; i++) {
        int t = map[upX][i];
        map[upX][i] = prev;
        prev = t;
    }
    for(int i = upX-1; i > 0; i--) {
        int t = map[i][C-1];
        map[i][C-1] = prev;
        prev = t;
    }
    for (int i = C-1; i >= 0; i--) {
        int t = map[0][i];
        map[0][i] = prev;
        prev = t;
    }
    for (int i = 1; i < upX; i++) {
        int t = map[i][0];
        map[i][0] = prev;
        prev = t;
    }
    
    prev = map[downX][downY];
    for (int i = 1; i < C; i++) {
        int t = map[downX][i];
        map[downX][i] = prev;
        prev = t;
    }
    for(int i = downX+1; i < R-1; i++) {
        int t = map[i][C-1];
        map[i][C-1] = prev;
        prev = t;
    }
    for (int i = C-1; i >= 0; i--) {
        int t = map[R-1][i];
        map[R-1][i] = prev;
        prev = t;
    }
    for (int i = R-2; i > downX; i--) {
        int t = map[i][0];
        map[i][0] = prev;
        prev = t;
    }
    
    map[upX][upY] = 0;
    map[downX][downY] = 0;
}

void solve() {
    
    while(T--) {
        
        spread();
        clean();
    }
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> R >> C >> T;
    
    map.resize(R, vector<int>(C));
    
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> map[i][j];
            if(map[i][j] == -1) {
                map[i][j] = 0;
                
                if(upX) {
                    downX = i;
                    downY = j;
                } else {
                    upX = i;
                    upY = j;
                }
            }
        }
    }
    
    solve();
    
    int res = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            res += map[i][j];
        }
    }
    
    cout << res << '\n';
    
    return 0;
}