[백준 17144][C++] 미세먼지 안녕! (Gold 5)

[문제보기]

 17144. 미세먼지 안녕!

17144번: 미세먼지 안녕!

 

[풀이방법]

이 문제는 미세먼지의 확산 & 공기청정기 순환 이 두 가지를 생각해줘야 한다.

 

1. 미세먼지 확산

이 부분에서 제일 중요한 부분은 동시다발적으로 확산이 일어나는 경우라는 것이다. 

그림으로 예를 들자면

이런 방식이 아니라,

이런 방식으로 동시다발적으로 확산이 진행된다는 뜻이다. 따라서 미세먼지를 확산을 진행할 때,

미세먼지의 양은 원래의 양을 기준으로 연산을 진행해야 된다. 

그렇게 때문에 필자는 미세먼지 확산을 연산하는 dust() 함수에서 temp 2차원 배열을 만들어 map 배열을 기준으로

temp배열을 채워준 다음 map 배열에 복사를 진행해주었다. 

 

2. 공기청정기 순환

이 부분에서는 위의 공기청정기는 반시계 방향으로 아래 공기청정기는 시계방향으로 순환이므로 이 두 가지 부분에 

대해서 각각 알고리즘을 만들어줘야 한다. 

필자는 처음 movdir[4] 배열에 상하좌우에 대한 데이터를 저장해놨기 때문에 movdir[4]의 인덱스를 사용하여

ccw[4](반시계), cw[4](시계) 방향에 대한 배열을 만들어주었다. 

 

공기청정기 순환 부분을 연산하는 air_clean() 함수에서는 공기청정기로 인해 미세먼지가 한 칸씩 밀리는 과정을

수행하기 위해 map 배열을 temp 배열에 복사를 한 후 연산을 진행해주었다. 

공기청정기 위치의 오른쪽 칸은 미세먼지가 밀리므로 0으로 만들어준 다음 한 칸씩 밀면서 map 배열에 데이터를 넣어주었다. 

[소스코드]

#include <iostream>
#include <queue>
using namespace std;

typedef struct _cleaner{
    int y;
    int x;
}Cleaner;

int n,m,t;
int map[50][50] = {0};
bool check[50][50];
Cleaner air_1, air_2;
pair<int, int> movdir[4] = {{-1,0}, {1,0}, {0, -1}, {0, 1}}; //상하좌우
//반시계 우 상 좌 하
int ccw[4] = {3, 0, 2, 1};
//시계 우 하 좌 상
int cw[4] = {3, 1, 2, 0};

void dust(){
    int temp[50][50] = {0};

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(map[i][j] > 0){
                int cnt = 0;
                for(int k=0; k<4; k++){
                    int nexty = i + movdir[k].first;
                    int nextx = j + movdir[k].second;

                    if(nexty < 0 || n <= nexty || nextx < 0 || m <= nextx) continue;
                    if(map[nexty][nextx] == -1) continue;

                    temp[nexty][nextx] += map[i][j]/5;
                    cnt++;
                }
                temp[i][j] += map[i][j] - ((map[i][j]/5)*cnt);
            }

            if(map[i][j] == -1){
                temp[i][j] = -1;
            }
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            map[i][j] = temp[i][j];
        }
    }
}

void air_clean(){
    int temp[50][50] = {0};
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            temp[i][j] = map[i][j];
        }
    }

    int y1 = air_1.y;
    int x1 = air_1.x+1;
    map[y1][x1] = 0;
    for(int i=0; i<4; i++){
        while(1){
            int nexty = y1 + movdir[ccw[i]].first;
            int nextx = x1 + movdir[ccw[i]].second;

            if(nexty == air_1.y && nextx == air_1.x) break;
            if(!(0 <= nexty && nexty <n && 0<=nextx && nextx <m)) break;

            
            map[nexty][nextx] = temp[y1][x1];
            y1 = nexty;
            x1 = nextx;
        }
    }


    int y2 = air_2.y;
    int x2 = air_2.x+1;
    map[y2][x2] = 0;
    for(int i=0; i<4; i++){
        while(1){
            int nexty = y2 + movdir[cw[i]].first;
            int nextx = x2 + movdir[cw[i]].second;

            if(nexty == air_2.y && nextx == air_2.x) break;
            if(!(0 <= nexty && nexty <n && 0<=nextx && nextx <m)) break;

            
            map[nexty][nextx] = temp[y2][x2];
            y2 = nexty;
            x2 = nextx;
        }
    }
}


int main(){
    cin.tie(0);
    cout.sync_with_stdio(false);

    cin >> n >> m >> t;
    bool flag = true;

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> map[i][j];
            if(map[i][j] == -1 && flag){
                flag = false;
                air_1.y = i;
                air_1.x = j;

                air_2.y = i+1;
                air_2.x = j;
            }
        }
    }

    while(t--){
        dust();
        air_clean();

    }

    int sum = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(map[i][j] > 0)
                sum += map[i][j];
        }
    }
    
    cout << sum ;
}

[해결 과정 중 실수한 부분]

미세먼지 확산하는 부분에 대해서는 금방 구현을 했지만,

공기청정기 순환 부분에서 반시계와 시계방향을 구현하는 것은 쉬었지만 코드가 너무 더러워졌다. (엄청 길어지고

삼중 for문 나오고....) 

블로그를 참고해서 movdir[4] 배열의 인덱스를 사용하여 ccw[4], cw[4] 배열을 만들어 순환시키는 방법을 사용하여 

공기청정기 순환을 구현해주었다.

 

[참고한 자료]

https://jaimemin.tistory.com/1205