[백준 17144] - 미세먼지 안녕!(C++)[골드4]

문제

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

17144번: 미세먼지 안녕!

---

 

문제 설명

문제가 굉장히 길고 복잡해 보입니다.

하지만 주목해야 할 포인트는 아래와 같습니다.

• 공기청정기의 열은 고정되어 있습니다.
• 미세먼지는 4방향으로 확산되고, 인접한 방향에 공기청정기나, 칸이 없다면 확산이 일어나지 않습니다.
  • 확산은 기준 칸의 미세먼지양의 5분의 1이 확산됩니다.
• 공기청정기의 바람은 바람의 방향대로 한칸씩 이동시키고, 시계방향과, 반시계방향이 있습니다.

 

먼지를 확산시켜야 합니다.

여기서 확산에는 큐와 배열 2개를 사용했습니다. (배열 2개를 사용한 이유는 아래 설명에 나옵니다)

 

우선 기본적으로 BFS를 진행했습니다.

배열의 값이 0보다 크다면 해당 칸은 미세먼지가 있는 것이고, 그러한 칸들을 확산하기 전에 큐에 모두 넣었습니다.

 

칸에서 4방향으로 탐색을하고, 이동할 수 있다면 먼지의 5분의 1을 더해주고, 기존 칸의 먼지는 5분의 1을 감소시켜 줬습니다.

이렇게 수정된 배열을 다시 기존배열로 만들어줬습니다.

 

💡여기서 왜 추가된 배열을 사용해야 하나?

저는 탐색을 하면서, 값들을 변경하고 싶었기 때문에, 배열을 하나만 쓴다면, 변경된 값들이 다음 확산에 영향을 주기 때문입니다.

이렇게 되면 먼지의 확산이 끝났습니다.

먼지의 확산이 끝났다면 공기청정기가 작동됩니다.

 

시계방향과 반시계 방향으로 미세먼지를 옮겨주는 작업이 반드시 필요합니다.

여기서 회전하는 순서가 굉장히 중요합니다. 

왜냐하면 순서가 이상하면, 옮겨줄 때 칸이 중복되어서 원래 있던 칸이 사라지기 때문입니다.

(하지만 저는 회전하는 순서를 마음대로 해서, 중복되는 칸의 원소들을 미리 추출해서 저장했습니다..)

 

미세먼지를 옮겨주다가, 만약 공기청정기로 미세먼지가 이동하면 그때의 먼지는 사라집니다.

배열의 원소들을 시계방향, 반시계방향으로 옮겨주는 알고리즘은 구글링을 하면 깔끔하게 나오기 때문에 참고하시면 될 거 같습니다.

 

이렇게 t초동 안 먼지의 확산, 공기청정기 작동을 반복하다가, t초가 되어서 배열에 먼지의 양을 계산하면 됩니다.

---

 

💻전체 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int r,c,t;
vector<vector<int> >ary;
int urow,ucol,drow,dcol;
int dir[4][2]={ {0,1},{0,-1},{1,0},{-1,0} };
void dust_move();
vector<pair<int,int> >mc;
queue<pair<int,int> >dust;
void air();
int main(){    
    cin>>r>>c>>t;
    ary.resize(r,vector<int>(c,0));
    for(int i=0; i<r; i++){
        for(int j=0; j<c;j++){
            cin>>ary[i][j];
            if(ary[i][j]==-1)
                mc.push_back(make_pair(i,j));
        }
    }
    urow = mc[0].first,ucol=mc[0].second,drow=mc[1].first,dcol=mc[1].second;
    //urow,ucol은 공기청정기 윗부분, drow,dcol은 공기청정기 아랫부분
    while(t--){
        dust_move();
        air();        
    }
    int answer=0;
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            if(ary[i][j]==-1){
                continue;
            }
            answer+=ary[i][j];
        }
    }
    cout<<answer<<endl;
}
void air(){ //공기청정기 작동. 시계방향, 반시계방향으로 공기청정기로 들어오는 미세먼지는 없어진다.
    //좌표 기준으로 반시계, 시계 방향
    //시계방향
    int temp =  ary[drow][c-1]; // 꼭짓점 값들을 미리 추출.
    int temp2=ary[r-1][c-1]; 
    int temp3=ary[r-1][0]; 
    for(int i=c-1; i>1; i--){     //위쪽
        ary[drow][i]=ary[drow][i-1];
    }
    ary[drow][1]=0; //공기청정기 바로 오른쪽 칸은 0이 된다.
    for(int i=r-1; i>drow; i--){ // 오른쪽
        if(i==drow+1){
            ary[i][c-1]=temp;
            continue;
        }
        ary[i][c-1]=ary[i-1][c-1];
    }
    for(int i=0;i<c-1;i++){ // 아래쪽
        if(i==c-2){
            ary[r-1][i]=temp2;
            continue;
        }
        ary[r-1][i]=ary[r-1][i+1];
    }
    for(int i=drow+1; i<r-1; i++){ //왼쪽
        if(i==r-2){
            ary[i][0]=temp3;
            continue;
        }
        ary[i][0]=ary[i+1][0];
    }
    //반시계 방향
    temp=ary[urow][c-1]; //미리 꼭짓점 값들을 추출함.
    temp2=ary[0][c-1];
    temp3=ary[0][0];
    for(int i=c-1; i>0; i--){ //아래
        if(ary[urow][i-1]==-1){
            ary[urow][i]=0;
            continue;
        }
        ary[urow][i]=ary[urow][i-1];
    }
    for(int i=0; i<urow; i++){ //오른쪽
        if(i==urow-1){
            ary[i][c-1]=temp;
            continue;
        }
        ary[i][c-1]=ary[i+1][c-1];
    }
    for(int i=0; i<c-1; i++){ //위쪽
        if(ary[0][i]==-1){
            continue;
        }
        if(i==c-2){
            ary[0][i]=temp2;
            continue;
        }
        ary[0][i]= ary[0][i+1];
    }
    for(int i=urow-1; i>0; i--){ //왼쪽
        if(i==1){
            ary[i][0]=temp3;
            continue;
        }
        ary[i][0]=ary[i-1][0];
    }
}
void dust_move(){ //여기까지는 잘 되는듯.
    
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            if(ary[i][j]>0){
                dust.push(make_pair(i,j));
            }
        }
    }
    vector<vector<int> >v;
    v.assign(r,vector<int>(c,0));
    v=ary;
    while(!dust.empty()){
        int row =dust.front().first, col = dust.front().second;
        int val = ary[row][col]/5;
        dust.pop();
        for(int i=0; i<4; i++){
            int nrow = row+dir[i][0], ncol=col+dir[i][1];
            if(nrow<0 || nrow >=r || ncol<0 || ncol>=c || ary[nrow][ncol]==-1){
                continue;
            }
            v[nrow][ncol]+=val;
            v[row][col]-=val;
        }
    }
    ary=v;
}

주석을 통해서 코드를 이해해 주십시오!!

😀느낀 점

• 추가된 배열의 사용은 반드시 필요한 단계이다.
  • 만약..? 추가된 배열을 사용하지 않는다면 어떻게 풀지는 잘 모르겠다!
• 탐색을 하는 동시에 queue에 원소를 넣어주고 싶었는데, 잘못된 알고리즘인 거 같았다.
  그래서 먼지의 확산을 시작하기 전에, 먼지를 체크해서 queue에 넣어줬다.
  • 사실 계속 r*c 배열을 탐색해서 큐에 넣는 작업을 하기 싫어서, bfs 내에서 queue에 삽입해 줬는데, 잘못된 접근이었던 것 같다.
• 시계방향, 반시계방향으로 원소를 밀어주는 알고리즘은 자주 쓰이는 거 같아서 확실하게 정리할 필요성이 있는 것 같다.
  • 나올 때마다 저렇게 막일을 하기엔 너무 시간이 부족하다!