17144번 : 미세먼지 안녕! [C++]

문제 링크

성공 여부(걸린 시간): 성공(1시간 7분 24초)

아이디어

해당 문제는 시뮬레이션 문제였다.

중요하게 생각할 동작이 아래와 같이 크게 2가지인데

 

1. 미세먼지의 확산

2. 공기청정기 작동

 

이에 맞춰 나누어 설명을 해보겠다.

1. 미세먼지의 확산 (spread_dust)

spread_dust 함수를 통해서 확산을 시켜주려고 설계를 했다.

 

해당 함수에서는 전체 입력을 받은 map 배열을 순회하면서 0보다 큰 값이 나오면 그 지점이 미세먼지가 위치하는 곳이기에

상하좌우로 확산될 수 있는 곳의 개수만큼 기존 미세먼지에는 ( - 기존 미세먼지 / 5 )를 해주고

확산되어 도달한 지점에는 ( + 기존 미세먼지 / 5 )을 해준다.

 

해당 동작에서 중요한 것은 만약 map 하나로 관리를 했다면 특정시간 i초라고 했을때

확산되어 추가된 미세먼지와 줄어든 값들이 이리저리 뒤섞여 올바르지 못한 값을 뽑아내기 때문에

추가와 감소에 대한 값들을 우선적으로 저장해줄 sum_arr를 만들어서 해당 배열에 저장해줬다.

 

모든 i초에 존재하던 미세먼지에 대해서 확산이 끝나 sum_arr가 완성되었다면

map에 더해줌으로써 해당 함수와 미세먼지 확산 동작이 마무리가 된다.

 

아래는 해당 함수의 코드이다.

void spread_dust() {
    vector<vector<int>> sum_arr(R + 1, vector<int>(C + 1, 0));
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            if (map[i][j] > 0) {
                for (int dir = 0; dir < 4; dir++) {
                    int mx = i + dx[dir];
                    int my = j + dy[dir];
                    int origin_dust_size = map[i][j];
                    // 뻗어나갈 수 있는 방향이다? -> 확산 
                    //can_spread는 (return x > 0 && y > 0 && x <= R && y <= C && map[x][y] != -1;)
                    if (can_spread(mx, my)) {
                        sum_arr[mx][my] += origin_dust_size / 5;
                        sum_arr[i][j] -= origin_dust_size / 5;
                    }
                }
            }
        }
    }
    // 반영
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            map[i][j] += sum_arr[i][j];
        }
    }
}

2. 공기청정기 작동 (action_air_fresher)

공기 순환을 수행할 action_air_fresher 함수를 만든다.

공기청정기의 동작

 

이 부분에서 막히는 경우가 많을 것이라고 생각한다.

 

우선 내가 생각한 부분은 높이가 2칸이고 너비가 1칸짜리인 map에서 -1로 표시된 공기청정기가

윗부분, 아랫부분의 동작의 방향이 다르기때문에 하나의 함수를 만들더라도 각 동작을 구분해주었다.

 

만약 윗부분이라면 반시계방향으로 동작을 해야한다. 동작은 반시계방향으로 내용물을 이동시킨다고 생각하면 편하다.

그리고 공기청정기로 들어간 미세먼지는 없어지고 공기청정기에서 새로 나오게 되는 공기는 Fresh하다는 점을 잊지말자

 

처음에는 큐에 넣고 빼면서 갱신해주려고 했으나 그렇게 일을 두 번할 필요 없이 배열을 역으로 갱신해주고자 했다.

이게 무슨 말이냐면 그림을 보면 이해가 쉽다.

실제 기존 미세먼지가 이동될 도착지에서 기존 미세먼지 값을 불러온다고 생각하면 편할 듯 하다.

 

ex) map[2][1] = map[1][1]

 

이런식으로 불러오는데 불러오는 방향은 반시계이나 불러오는 순서는 기존 바람방향과 반대이다.

반대쪽도 동일하게 해주는데 함수에서 공기청정기의 윗부분인지 아닌지를 함수 파라미터로 받아서

(나는 is_clock을 통해 파악했음) 각 부분에 맞는 재귀를 통해 한칸씩 이동시켜주었다.

 

해당 부분에 대해서는 코드를 보는 것이 이해가 더 쉬울듯 하다.

참고로 공기청정기에서 공기가 나오는 부분은 공기청정기의 동작이 완료된 직후에

        map[air_fresher.first][2] = 0;  
        map[air_fresher.second][2] = 0;

 

이렇게 초기화를 해주면 완벽하다.

void action_air_fresher(int x, int y, bool is_clock) {
    //반시계 방향이면 시계방향으로 앞의 값 불러오기
    if (!is_clock) {
        //올라가야함
        if (y == 1 && x > 1) {
            map[x][y] = map[x - 1][y];
            action_air_fresher(x - 1, y, is_clock);
        }
        //우측으로 가야함
        else if (x == 1 && y < C) {
            map[x][y] = map[x][y + 1];
            action_air_fresher(x, y + 1, is_clock);
        }
        //아래로 가야함
        else if (y == C && x < air_fresher.first) {
            map[x][y] = map[x + 1][y];
            action_air_fresher(x + 1, y, is_clock);
        }
        //좌측으로 가야함 (공기청정기 입구까지 도달)
        else if (x == air_fresher.first && y > 2) {
            map[x][y] = map[x][y - 1];
            action_air_fresher(x , y - 1, is_clock);
        }
    }
    //시계 방향이면 반시계 방향으로 앞의 값 불러와서 저장
    else {
        //아래로 가야함
        if (y == 1 && x < R) {
            map[x][y] = map[x + 1][y];
            action_air_fresher(x + 1, y, is_clock);
        }
        //우측으로 가야함
        else if (x == R && y < C) {
            map[x][y] = map[x][y + 1];
            action_air_fresher(x, y + 1, is_clock);
        }
        //올라가야함
        else if (y == C && x > air_fresher.second) {
            map[x][y] = map[x - 1][y];
            action_air_fresher(x - 1, y, is_clock);
        }
        //좌측으로 가야함 (공기청정기 입구까지 도달)
        else if (x == air_fresher.second && y > 2) {
            map[x][y] = map[x][y - 1];
            action_air_fresher(x , y - 1, is_clock);
        }
    }
}

풀이 코드

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

int R, C;
pair<int, int> air_fresher = { 0, 0 };
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int map[51][51] = { {0,}, };

bool can_spread(int x, int y) {
    return x > 0 && y > 0 && x <= R && y <= C && map[x][y] != -1;
}

void spread_dust() {
    vector<vector<int>> sum_arr(R + 1, vector<int>(C + 1, 0));
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            if (map[i][j] > 0) {
                for (int dir = 0; dir < 4; dir++) {
                    int mx = i + dx[dir];
                    int my = j + dy[dir];
                    int origin_dust_size = map[i][j];
                    if (can_spread(mx, my)) {
                        sum_arr[mx][my] += origin_dust_size / 5;
                        sum_arr[i][j] -= origin_dust_size / 5;
                    }
                }
            }
        }
    }
    // 반영
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            map[i][j] += sum_arr[i][j];
        }
    }
}

void action_air_fresher(int x, int y, bool is_clock) {
    //반시계 방향이면 시계방향으로 앞의 값 불러오기
    if (!is_clock) {
        //올라가야함
        if (y == 1 && x > 1) {
            map[x][y] = map[x - 1][y];
            action_air_fresher(x - 1, y, is_clock);
        }
        //우측으로 가야함
        else if (x == 1 && y < C) {
            map[x][y] = map[x][y + 1];
            action_air_fresher(x, y + 1, is_clock);
        }
        //아래로 가야함
        else if (y == C && x < air_fresher.first) {
            map[x][y] = map[x + 1][y];
            action_air_fresher(x + 1, y, is_clock);
        }
        //좌측으로 가야함 (공기청정기 입구까지 도달)
        else if (x == air_fresher.first && y > 2) {
            map[x][y] = map[x][y - 1];
            action_air_fresher(x , y - 1, is_clock);
        }
    }
    //시계 방향이면 반시계 방향으로 앞의 값 불러와서 저장
    else {
        //아래로 가야함
        if (y == 1 && x < R) {
            map[x][y] = map[x + 1][y];
            action_air_fresher(x + 1, y, is_clock);
        }
        //우측으로 가야함
        else if (x == R && y < C) {
            map[x][y] = map[x][y + 1];
            action_air_fresher(x, y + 1, is_clock);
        }
        //올라가야함
        else if (y == C && x > air_fresher.second) {
            map[x][y] = map[x - 1][y];
            action_air_fresher(x - 1, y, is_clock);
        }
        //좌측으로 가야함 (공기청정기 입구까지 도달)
        else if (x == air_fresher.second && y > 2) {
            map[x][y] = map[x][y - 1];
            action_air_fresher(x , y - 1, is_clock);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> R >> C >> T;
    bool is_up = true;
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            cin >> map[i][j];
            if (map[i][j] == -1) {
                if (is_up) {
                    air_fresher.first = i;
                    is_up = false;
                }
                else {
                    air_fresher.second = i;
                }
            }
        }
    }

    while (T-- != 0) {
        // 미세먼지 확산
        spread_dust();

        // 공기청정기 작동
        // 반시계
        action_air_fresher(air_fresher.first - 1, 1, false);
        // 시계
        action_air_fresher(air_fresher.second + 1, 1, true);

        //송풍구 바로 앞은 싱싱한 공기
        map[air_fresher.first][2] = 0;
        map[air_fresher.second][2] = 0;
    }
    int sum = 2;
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            sum += map[i][j];
        }
    }
    cout << sum;
    return 0;
}