백준 17144 - 미세먼지 안녕!

 

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

17144번: 미세먼지 안녕!

문제 설명

---

(r, c)는 r행 c열을 의미한다. 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다.

공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

 

1초 동안 아래 적힌 일이 순서대로 일어난다.

 

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.

2. (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.

2. 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.

4. 확산되는 양은 Ar,c/5이고 소수점은 버린다.

5. (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.

 

공기청정기가 작동한다.

 

1. 공기청정기에서는 바람이 나온다.

2. 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.

3. 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.

4. 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

 

 

접근 방법

---

시뮬레이션 알고리즘으로 주어진 조건을 하나씩 넣으면 문제가 해결됩니다. ㅠㅠ 하지만 시뮬레이션은 보통 많은 조건으로 복잡하고 시간복잡도 또한 계산해야하죠.. 

1. spread(), cleaning() 함수를 만든다.

2. 시간 만큼 먼지를 흡수한다.

 

첫째, 이 문제에서 copy()를 통해  먼지가 이동 정보를 업데이트를 하는데 수월하도록 함. 

둘째, 백터의 성질을 이용하여  첫번째 항목에는 먼지가 이동하고 남아있는 먼지 수, 이후 이동된 먼지를 삽입하면서 sum() 함수를 이용하여 마지막에 해당 칸 안에 모든 먼지를 합치기 편하게 함.

 

저는 확인을 위해 중간과정에 print()함수를 사용하여 올바른 진행을 확인했습니다!!!! 삭제하셔도 무방합니다~~~

 

 

코드

---

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int r,c,t;
int ans;
int cleaner_x1,cleaner_y1;
int cleaner_x2,cleaner_y2;
vector<int>room[51][51];
vector<int>temp_room[51][51];
vector<pair<int,int> >cleaner;
int dy[]={-1,0,1,0};
int dx[]={0,-1,0,1};

void print(){
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            if(room[i][j][0]==-1){cout<<"- ";continue;}
            cout<<room[i][j][0]<<" ";
        }
        cout<<"\n";
    }
}

void sum(){
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            int total=0;
            int my_dust = room[i][j][0];	//전파된 모든 먼지의 양을 합치는 과정
            for(int k=1;k<room[i][j].size();k++){
                total+=room[i][j][k];
            }
            room[i][j].clear();
            room[i][j].push_back(total+my_dust);
        }
    }
}

void spread(){	//전파 과정
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
        	// 공기청정기가 있거나 먼지가 없는 경우는 제외하고 진행한다.
            if(room[i][j][0] == -1 || room[i][j][0]==0)continue;
            //cout<<"i ,j :"<<i<<" "<<j<<"\n";
            int dust=room[i][j][0];	//가지고 있는 먼지수
            int moving_dust = floor(dust/5);// 전파된다면 전파 가능한 먼지 양
            for(int k=0;k<4;k++){
                int ny = i+ dy[k];
                int nx = j +dx[k];
                if( ((ny>=1&&ny<=r)&&(nx>=1&&nx<=c)) ){	// 범위 확인
                    if(room[ny][nx][0]== -1){continue;}	//범위가 공기청정기일때 예외 처리
                    room[ny][nx].push_back(moving_dust);
                    dust -= moving_dust; //전체 먼지에서 차감
                }
            
            }
            room[i][j][0]=dust;	//남은 먼지 저장
        }
    }
    sum();	//먼지를 합치는 과정
    print();
}
//a-> b copy 
void copy(vector<int>a[51][51] ,vector<int>b[51][51]){
	//push_back으로 [0]번째에 넣는 과정을 추후에 진행하므로 진행전 초기화를 진행
    for(int i=1;i<=r;i++){	
        for(int j=1;j<=c;j++){
            b[i][j].clear();
        }
    }
    //복사 시작
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            b[i][j].push_back(a[i][j][0]);
        }
    }
    
}
void cleaning(){
    //첫번째 반 시계, 두번째 시계
    cleaner_y1=cleaner[0].first;
    cleaner_y2=cleaner[1].first;
    copy(room,temp_room);
    
    //첫번째 공기청정기 클리닝
    room[cleaner_y1][2][0]=0;
    for(int i=2;i<=c-1;i++){
        room[cleaner_y1][i+1][0]=temp_room[cleaner_y1][i][0];
    }
    for(int i=cleaner_y1;i>=2;i--){
        room[i-1][c][0]=temp_room[i][c][0];
    }
    for(int i=c;i>=2;i--){
        room[1][i-1][0]=temp_room[1][i][0];
    }
    for(int i=1;i<=cleaner_y1-2;i++){
        room[i+1][1][0]=temp_room[i][1][0];
    }
    ans+=temp_room[cleaner_y1-1][1][0];

	//밑에 있는 공기청정기 클리닝
    room[cleaner_y2][2][0]=0;
    for(int i=2;i<=c-1;i++){
        room[cleaner_y2][i+1][0]=temp_room[cleaner_y2][i][0];
    }
    for(int i=cleaner_y2;i<=r-1;i++){
        room[i+1][c][0]=temp_room[i][c][0];
    }
    for(int i=c;i>=2;i--){
        room[r][i-1][0]=temp_room[r][i][0];
    }
    for(int i=r;i>=cleaner_y2+2;i--){
        room[i-1][1][0]=temp_room[i][1][0];
    }
    ans+=temp_room[cleaner_y2+1][1][0];
    print();
}


int main(){
    cin>>r>>c>>t;
    int real_ans=0;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            int temp;
            cin>>temp;
            real_ans+=temp;
            room[i][j].push_back(temp);
            if(temp== -1){
                cleaner.push_back(make_pair(i,j));
            }
        }
    }
    
    while(t--){
        print();
        spread();
        cleaning();
    }
    cout<<real_ans+2-ans<<"\n";
    return 0;
}

 

funny algorithms ~ ^0^