17144번-미세먼지 안녕

문제

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

17144번: 미세먼지 안녕!

---

접근방법

1) 접근 사고

특별한 알고리즘이 없지만 인덱스의 값 설정에 주의해서 풀어야 하는 문제였습니다. Spread, upper_move, Bottom_move 3가지 함수로 각 동작들을 정의하여 문제를 해결하였습니다.

 

2) 시간 복잡도

O(N^2)

 

3) 배운 점

람다식을 사용할때 캡쳐영역을 전체로 사용할 때 밖에 있는 변수와 이름이 같은 것을 사용하면 안된다는것을 알게 되었습니다. 만약 사용하게 되면 UB(Undefind Behavior)가 발생합니다.

 

4) PS

아니 UB 작동이 안되어야 하는거 아닌가??(컴파일러마다 작동이 될 수도 안 될수도.... 정의가 안 되어있기 때문에 모릅니다.)

---

정답 코드

/**
 * 1.미세먼지가 동서남북으로 확산된다(공기청정기가 있거나 범위 초가시 제외
 * 2.확산되는 미세먼지양은 A(r,c) / 5
 * 3.남은 미세먼지양은 A(r,c) - (A(r,c)/ 5) * (확산된 방향의 개수)
 *
 * 1.위쪽 공기청정기는 반시계 방ㅇ향
 * 2.아래쪽은 시계 방향
 * 3.공기청정기쪽으로 들어오는 미세먼지는 사라진다
 */
 
#include<bits/stdc++.h>
 
using namespace std;
 
const int MAX = 51;
int board[MAX][MAX];
int r, c, t;
 
int my[] = {-1, 0, 1, 0};
int mx[] = {0, 1, 0, -1};
pair<int, int> condi[2];
 
int main() {
    cin >> r >> c >> t;
    bool condiflag = true;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> board[i][j];
            if (condiflag && board[i][j] == -1) {
                condi[0] = {i, j};
                condiflag = false;
            } else if (!condiflag && board[i][j] == -1) {
                condi[1] = {i, j};
            }
        }
    }
 
    auto spread = [&](){
        int tmpboard[MAX][MAX];
        fill(&tmpboard[0][0], &tmpboard[MAX - 1][MAX - 1], 0);
        tmpboard[condi[0].first][condi[0].second] = -1;
        tmpboard[condi[1].first][condi[1].second] = -1;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (board[i][j] != -1) {
                    if (board[i][j] >= 5) {
                        int cnt = 0;
                        vector<pair<int, int>> v;
                        for (int d = 0; d < 4; d++) {
                            int ny = i + my[d];
                            int nx = j + mx[d];
                            if (ny >= 0 && ny < r && nx >= 0 && nx < c && board[ny][nx] != -1) {
                                cnt++;
                                v.push_back({ny, nx});
                            }
                        }
 
                        for (int k = 0; k < v.size(); k++) {
                            tmpboard[v[k].first][v[k].second] += board[i][j] / 5;
                        }
                        tmpboard[i][j] += board[i][j] - ((board[i][j] / 5) * cnt);
                    } else {
                        tmpboard[i][j] += board[i][j];
                    }
                }
            }
        }
        memcpy(board, tmpboard, sizeof(board));
    };
 
    auto upper_move = [&](){
        //좌
        int cy = condi[0].first;
        for(int i = cy - 1; i > 0; i--){
            board[i][0] = board[i - 1][0];
        }
        for(int i = 0; i < c - 1; i++){
            board[0][i] = board[0][i + 1];
        }
 
        for(int i = 0; i < cy; i++){
            board[i][c - 1] = board[i + 1][c - 1];
        }
        for(int i = c - 1; i > 1; i--){
            board[cy][i] = board[cy][i - 1];
        }
        board[cy][1] = 0;
        return;
    };
 
    auto bottom_move = [&](){
        int cy = condi[1].first;
        int R = r - 1;
        int C = c - 1;
 
        for(int i = cy + 1; i < R; i++){
            board[i][0] = board[i+1][0];
        }
        for(int i = 0; i < c; i++){
            board[R][i] = board[R][i + 1];
        }
        for(int i = R; i > cy; i--){
            board[i][C] = board[i - 1][C];
        }
        for(int i = C; i > 1; i--){
            board[cy][i] =board[cy][i - 1];
        }
        board[cy][1] = 0;
    };
 
    for (int i = 0; i < t; i++) {
        spread();
        upper_move();
        bottom_move();
    }
 
    int sum = 0;
    for(int i =0; i < r; i++){
        for(int j =0; j <c; j++){
            if(board[i][j] != -1)
            sum += board[i][j];
        }
    }
    cout <<sum <<"\n";
}