[C++] 미세먼지 안녕!

[문제]

17144번: 미세먼지 안녕! (acmicpc.net)

17144번: 미세먼지 안녕!

[문제 풀이]

시뮬레이션 문제이다.

문제에서 주어진 조건은 크게 1. 먼지를 확산 시켜라. 2. 공기청정기 바람을 이용해서 배열을 돌려라. 의 2가지 조건이다.

지문이 길다고 어려운것이 아니니 1번부터 천천히 해보자.

 

1번의 조건을 나눠보면 크게 a. 공기청정기로 가면 안된다. b. 범위내에서 이루어져야 한다. c. 독립적으로 영향을 준다. 의 3가지로 나눌 수 있다.

a번과 b번은 여태까지 다른 문제에서 여러번 해왔던 벽과 범위내라고 생각하면 쉬우니 이해가 되지만 c번의 경우 헷갈리는 부분이 있으니 주의해야 한다.

 

문제에서 주어진 경우인데 해당 경우를 잘 생각해보면 30은 양옆과 아래의 3칸으로 보내주니 30 - (30 / 5) * 3 의 값인 12가 나와야 하지만 보기에선 15가 되어있다.

이유로는 옆에있는 7과 아래에있는 10이 영향을 주었기 때문인데 7/5 인 1과 10/5인 2를 더해서 12 + (1 + 2 ) 가 되어서 15가 된것이다.

이 부분을 코드로 작성할때 주의사항이 30이 먼저 영향을 주면 7이 13이 되고 13에서 다시 왼쪽과 아래한테 주면 예시와 같은 그림이 나오지 않는다.

그렇기에 이를 막기 위해 arr 배열과 vec 배열을 만들어서 arr배열에서 사방에 더해주는 값을 vec에 넣어주고 arr배열은 해당값이 빼진 결과만 저장을 한 뒤, 모든 확산이 끝났을 때 arr 배열과 vec 배열을 더해주는 것으로 영향을 독립적으로 만들어야 한다.

 

2번의 경우 for문을 이용해서 시계방향과 반시계 방향으로 숫자를 한번씩 넘겨주고 이제 t번만큼 1번 -> 2번의 순서대로 모두 돌린뒤에 남은 arr 배열의 -1을 제외한 모든 값을 더해주면 답이 된다.

[회고]

2번의 경우 문제를 보고 윗쪽은 반시계 아래쪽은 시계 방향으로 돌렸는데 그러다 보니 숫자가 마지막에 밀리는 값을 제어해야 해서 코드가 더 더러워졌다.

반대로 윗쪽을 시계방향 순서로 Down -> Left -> Up -> Right 순서대로 돌리면 공기청정기의 윗칸만 제거하고 숫자를 넘겨줄 필요없이 쉽게 구현이 가능하다.

 

밑의 코드에서는 문제에서 나온대로 Right -> Up -> Left -> Down 순서대로 했지만 해당 방법을 알고 있다면 훨씬 문제가 쉽게 풀렸을 것이다.

[코드]

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n,m,t;
int arr[51][51];
int vec[51][51];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
vector<int> purifier;
queue<pair<int, int> > q;

void vecEqual(){
    for(int i = 0;i<n;i++){
        for(int j =0;j<m;j++){
            vec[i][j] = 0;
        }
    }
    return;
}

void arrEqual(){
    for(int i = 0;i<n;i++){
        for(int j =0;j<m;j++){
            arr[i][j] = vec[i][j] + arr[i][j];
        }
    }
    return;
}

int dustAdd(){
    int answer = 0;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(arr[i][j] != -1){
                answer += arr[i][j];
            }
        }
    }
    return answer;
}

int moveDown(int x1, int x2, int y, int cnt){
    int answer = arr[x2][y];
    for(int i = x2;i>=x1 + 1;i--){
        if(arr[i][y] == -1){
            continue;
        }
        arr[i][y] = arr[i -1 ][y];
    }
    arr[x1 + 1][y] = cnt;
    return answer;
}

int moveLeft(int x, int cnt){
    int answer = arr[x][0];

    for(int i = 0;i<m - 1;i++){
        arr[x][i] = arr[x][i + 1];
    }
    arr[x][m - 2] = cnt;
    return answer;
}

int moveUp(int x1, int x2, int y, int cnt){
    int answer = arr[x2][y];
    for(int i = x2; i<x1; i++){
        if(arr[i][y] == -1){
            continue;
        }
        arr[i][y] = arr[i + 1][y];
    }
    arr[x1 - 1][y] = cnt;
    return answer;
}

int moveRight(int x){
    int cnt = arr[x][m - 1];

    for(int i = m - 1; i > 1; i--){
        arr[x][i] = arr[x][i - 1];
    }
    arr[x][1] = 0;
    return cnt;
}

void qPush(){
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(arr[i][j] != 0 && arr[i][j] != -1){
                q.push(make_pair(i,j));
            }
        }
    }
    return;
}

void expand(int x, int y){
    int cur = arr[x][y];
    int flag = 0;
    for(int i = 0;i<4;i++){
        int nextX = x + dx[i];
        int nextY = y + dy[i];
        if(nextX >= 0 && nextX < n && nextY >= 0 && nextY < m){
            if(arr[nextX][nextY] != -1){
                vec[nextX][nextY] += cur / 5;
                // arr[nextX][nextY] += cur / 5;
                flag++;
            }
        }
    }
    arr[x][y] = arr[x][y] - (arr[x][y] / 5 * flag);
    return;
}

void simu(){

    while(t--){
        vecEqual();
        while(q.size() > 0){
            expand(q.front().first,q.front().second);
            q.pop();
        }
        arrEqual();
        //공기청정기 첫번째 기준으로 반시계, 두번째 기준으로 시계
        //반시계
        int temp = moveRight(purifier[0]);
        temp = moveUp(purifier[0], 0, m - 1,temp);
        temp = moveLeft(0, temp);
        temp = moveDown(0,purifier[0],0,temp);

        // //시계
        temp = moveRight(purifier[1]);
        temp = moveDown(purifier[1], n - 1, m - 1, temp);
        temp = moveLeft(n - 1,temp);
        temp = moveUp(n - 1, purifier[1], 0, temp);

        qPush();
    }

    return;
}

int main(){
    cin>>n>>m>>t;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            cin>>arr[i][j];
            if(arr[i][j] == -1){
                purifier.push_back(i);
            }
            else if(arr[i][j] != 0){
                q.push(make_pair(i,j));
            }
        }
    }
    simu();
    cout<<dustAdd()<<endl;
    return 0;
}