[algorithm] 백준 - 미세먼지 안녕!

이 문제는 삼성 SW 기출 문제이다. 시뮬레이션이다.

 

총 두가지 연산이 요구된다.

 

미세먼지 확산

expand()

1. 네방향 확산

인접한 방향에 -1 혹은 칸이 있는지 확인, 있다면 그 쪽은 확산이 안된다.

2. (r,c)에 위치한 값 / 5로 확산된다.

3. (r,c)에는 (r,c)에 위치한 값 - (r,c)에 위치한 값 / 5 * 확산되는 방향 개수로 설정된다.

 

확산시킬 때 유의할 점은 확산되는 값이 변하기 전 값에서 계산되어야 하므로

원본 값을 변환시키는 것이 아닌 확산되어 더해지는 값과 확산해서 없어지는 미세먼지 값을 따로 저장해두고

원본 값에 반영하는 형태로 구현해야한다.

 

void expand(){
    int spreadNum = 0;
    int weight[50][50];
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            weight[i][j] = 0;
        }
    }
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            if(i == cleanMachineDown.first && j == cleanMachineDown.second) continue;
            if(i == cleanMachineUp.first && j == cleanMachineUp.second) continue;
            if(vertex[i][j] != 0){
                spreadNum = vertex[i][j] / 5;
                vector<pair<int,int>> directionVector = getDirection(i,j);
                for(int k = 0; k < directionVector.size(); k++){
                    weight[directionVector[k].first][directionVector[k].second] += spreadNum;
                    weight[i][j] -= spreadNum;
                }
            }
        }
    }
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            vertex[i][j] += weight[i][j];
        }
    }
}

 

공기청정기 순환

clean()

1. 위쪽은 반시계 순환, 아래는 시계 순환

2. 바람 방향대로 1초에 한칸씩 이동된다.

3. 공기청정기로 들어간 값은 없어진다.

 

아래에서 cleanMachineUp과 cleanMachineDown은 공기청정기가 위치한 좌표를 의미한다.

따라서 자료형을 pair<int,int> 로 설정했다.

 

위쪽에 위치한 공기청정기부터 살펴보면,

1. 아래로 내려가는 방향

2. 왼쪽으로 가는 방향

3. 위쪽으로 올라가는 방향

4. 오른쪽으로 가는 방향

으로 미세먼지가 이동했을 때 빈 곳을 채워주는 형태로 구현할 수 있다.

 

index로 잡아보면 이렇다.

moveDown(0,cleanMachineUp.first - 2,cleanMachineUp.second);// (up, dp, y)

moveLeft(cleanMachineUp.second, c, 0); // (lp, rp, x)

moveUp(0, cleanMachineUp.first, c - 1); // (up, dp, y)

moveRight(c - 2, cleanMachineUp.second, cleanMachineUp.first); // (rp, lp, x)

 

아래쪽에 위치한 공기청정기의 경우,

1. 위로 올라가는 방향

2. 왼쪽으로 가는 방향

3. 아래로 내려가는 방향

4. 오른쪽으로 가는 방향

으로 미세먼지가 이동했을 때 빈 곳을 채워주는 형태로 구현할 수 있다.

 

index로 잡아보면 이렇다.

 

moveUp(cleanMachineDown.first + 1, r - 1, cleanMachineDown.second); //(up, dp, y)

moveLeft(cleanMachineDown.second, c, r - 1); // (lp, rp, x)
    
moveDown(cleanMachineDown.first, r - 2, c -1); // (up, dp, y)
    
moveRight(c - 2, cleanMachineDown.second, cleanMachineDown.first); // (rp, lp, x)

 

참고로 오른쪽으로 움직일 때 공기청정기에서 나오는 공간은 미세먼지가 없으므로 0으로 설정한다.

 

vertex[cleanMachineUp.first][cleanMachineUp.second + 1] = 0;
vertex[cleanMachineDown.first][cleanMachineDown.second + 1] = 0;

 

전체 코드는 이렇다.

 

//미세먼지 안녕!
#include <iostream>
#include <vector>
using namespace std;

pair<int,int> direct[] = {{0,1},{0, -1}, {1,0}, {-1, 0}};
int vertex[50][50];
pair<int,int> cleanMachineUp = {-1,-1};
pair<int,int> cleanMachineDown = {-1,-1};
int r, c, t;
vector<pair<int,int>> getDirection(int x, int y){
    vector<pair<int,int>> directionVector;
    for(int i = 0; i < 4; i++){
        int dx = x + direct[i].first;
        int dy = y + direct[i].second;
        if(dx < r && dy < c && dx >= 0 && dy >= 0){
            if(dx == cleanMachineDown.first && dy == cleanMachineDown.second)continue;
            if(dx == cleanMachineUp.first && dy == cleanMachineUp.second) continue;
            directionVector.push_back({dx,dy});
        }
    }
    return directionVector;
}
void moveDown(int up, int dp, int y){
    for(int i = dp; i >= up; i--){
        vertex[i + 1][y] = vertex[i][y];
    }
}
void moveLeft(int lp, int rp, int x){
    for(int i = lp; i < rp - 1; i++){
        vertex[x][i] = vertex[x][i + 1];
    }
}
void moveRight(int rp, int lp, int x){
    for(int i = rp; i > lp; i--){
        vertex[x][i + 1] = vertex[x][i];
    }
}
void moveUp(int up, int dp, int y){
    for(int i = up; i < dp; i++){
        vertex[i][y] = vertex[i + 1][y];
    }
}
void clean(){
    moveDown(0,cleanMachineUp.first - 2,cleanMachineUp.second);
    moveLeft(cleanMachineUp.second, c, 0);
    moveUp(0, cleanMachineUp.first, c - 1);
    moveRight(c - 2, cleanMachineUp.second, cleanMachineUp.first);
    vertex[cleanMachineUp.first][cleanMachineUp.second + 1] = 0;
    moveUp(cleanMachineDown.first + 1, r - 1, cleanMachineDown.second);
    moveLeft(cleanMachineDown.second, c, r - 1);
    moveDown(cleanMachineDown.first, r - 2, c -1);
    moveRight(c - 2, cleanMachineDown.second, cleanMachineDown.first);
    vertex[cleanMachineDown.first][cleanMachineDown.second + 1] = 0;
}
void expand(){
    int spreadNum = 0;
    int weight[50][50];
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            weight[i][j] = 0;
        }
    }
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            if(i == cleanMachineDown.first && j == cleanMachineDown.second) continue;
            if(i == cleanMachineUp.first && j == cleanMachineUp.second) continue;
            if(vertex[i][j] != 0){
                spreadNum = vertex[i][j] / 5;
                vector<pair<int,int>> directionVector = getDirection(i,j);
                for(int k = 0; k < directionVector.size(); k++){
                    weight[directionVector[k].first][directionVector[k].second] += spreadNum;
                    weight[i][j] -= spreadNum;
                }
            }
        }
    }
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            vertex[i][j] += weight[i][j];
        }
    }
}
void print(){
    cout << "\n";
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            cout << vertex[i][j] << " ";
        }
        cout << "\n";
    }
}

int getAnswer(){
    int answer = 0;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            if(vertex[i][j] >= 1)
                answer += vertex[i][j];
            }
        }
    return answer;
}
int main(void){
    cin >> r >> c >> t;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            cin >> vertex[i][j];
        }
    }
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            if(vertex[i][j] == -1 && vertex[i+1][j] == -1){
                cleanMachineUp = {i,j};
                cleanMachineDown = {i+1, j};
            }
        }
    }
    for(int i = 0; i < t; i++){
        expand();
        //print();
        clean();
        //print();
    }
    cout << getAnswer();
}