[BOJ/백준 17144][C++] 미세먼지 안녕!

문제

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

백준 17144

백준 17144

백준 17144

 

문제 내용

R*C 격자 판이 있고, 1열에는 공기청정기가 있다.

매 초마다 미세먼지는 확산하게 되며, 미세먼지 확장 이후에는 공기청정기의 순환에 따라 먼지가 이동한다.

미세먼지 확산 시, 공기청정기가 있는 곳이나 격자 판 밖으로는 확산되지 않는다. (확산되는 미세먼지 양은 사진 참고)

공기청정기는 위의 사진처럼, 윗부분은 반시계 방향, 아랫부분은 시계방향으로 공기를 순환시키며, 공기청정기에서 나가는 바람은 먼지가 없고, 공기청정기로 들어가는 미세먼지는 모두 정화된다.

 

문제 풀이

문제에 나온 과정대로 함수를 나누어 구현하면 된다.

1. 미세먼지 확산

2. 공기청정기 작동

3. 격자 판의 미세먼지 합 구하기

(1,2번은 매 초마다 반복하고, 3번은 마지막에 1번만 실행)

 

1. 미세먼지 확산

미세먼지가 존재하는 모든 칸에 대해서 상하좌우를 확인하고, 가능하다면 확산 후 자기 자신의 먼지양을 줄이면 된다.

void extendsDust() {
    vector<vector<int>> ccopy(r + 1, vector<int>(c + 1, 0));
    // 이번에 확산되며 생긴 먼지인지 아닌지 구분하려고 생성
    copy(arr.begin(), arr.end(), ccopy.begin()); 

    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            if (ccopy[i][j] <= 0)
                continue; // 비어있던가, 공기청정기이면 continue;

            int cnt = 0;
            for (int k = 0; k < 4; k++) {
                int nr = i + dr[k];
                int nc = j + dc[k];

                if (nr >= 1 && nc >= 1 && nr <= r && nc <= c && ccopy[nr][nc] != -1) {
                    arr[nr][nc] += (ccopy[i][j] / 5);
                    cnt++;
                }
            }
            arr[i][j] -= (ccopy[i][j] / 5) * cnt;
        }
    }
}

 

2. 공기청정기 작동

윗부분의 회전과, 아랫부분의 회전을 나누어 함수로 만들었다.

airCleaner는 공기청정기가 위치한 행 번호로, 0번에 윗부분, 1번에 아랫부분 행 번호가 담겨있다. 

void operateTopAirCleaner() {
    // 반시계 방향으로 회전
    for (int i = airCleaner[0] - 1; i > 1; i--) {
        arr[i][1] = arr[i - 1][1];
    }

    for (int i = 1; i < c; i++) {
        arr[1][i] = arr[1][i + 1];
    }

    for (int i = 1; i < airCleaner[0]; i++) {
        arr[i][c] = arr[i + 1][c];
    }

    for (int i = c; i > 2; i--) {
        arr[airCleaner[0]][i] = arr[airCleaner[0]][i - 1];
    }
    arr[airCleaner[0]][2] = 0;
}

void operateBottomAirCleaner() {
    // 시계 방향으로 회전;
    for (int i = airCleaner[1] + 1; i < r; i++) {
        arr[i][1] = arr[i + 1][1];
    }

    for (int i = 1; i < c; i++) {
        arr[r][i] = arr[r][i + 1];
    }

    for (int i = r; i > airCleaner[1]; i--) {
        arr[i][c] = arr[i - 1][c];
    }

    for (int i = c; i > 2; i--) {
        arr[airCleaner[1]][i] = arr[airCleaner[1]][i - 1];
    }
    arr[airCleaner[1]][2] = 0;
}

void operateAirCleaner() {
    operateTopAirCleaner();
    operateBottomAirCleaner();
}

 

3.  격자 판의 미세먼지 합 구하기

int accumulateDust() {
    int ssum = 0;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            if (arr[i][j] == -1)
                continue;
            ssum += arr[i][j];
        }
    }
    return ssum;
}

 

전체 코드는 아래와 같다.

 

전체 코드

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

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, 1, -1};

int r, c, t;
vector<vector<int>> arr;
vector<int> airCleaner;

void extendsDust() {
    vector<vector<int>> ccopy(r + 1, vector<int>(c + 1, 0));
    copy(arr.begin(), arr.end(), ccopy.begin()); // 이번에 확산되며 생긴 먼지인지 아닌지 구분하려고 생성

    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            if (ccopy[i][j] <= 0)
                continue; // 비어있던가, 공기청정기이면 continue;

            int cnt = 0;
            for (int k = 0; k < 4; k++) {
                int nr = i + dr[k];
                int nc = j + dc[k];

                if (nr >= 1 && nc >= 1 && nr <= r && nc <= c && ccopy[nr][nc] != -1) {
                    arr[nr][nc] += (ccopy[i][j] / 5);
                    cnt++;
                }
            }
            arr[i][j] -= (ccopy[i][j] / 5) * cnt;
        }
    }
}

void operateTopAirCleaner() {
    // 반시계 방향으로 회전
    for (int i = airCleaner[0] - 1; i > 1; i--) {
        arr[i][1] = arr[i - 1][1];
    }

    for (int i = 1; i < c; i++) {
        arr[1][i] = arr[1][i + 1];
    }

    for (int i = 1; i < airCleaner[0]; i++) {
        arr[i][c] = arr[i + 1][c];
    }

    for (int i = c; i > 2; i--) {
        arr[airCleaner[0]][i] = arr[airCleaner[0]][i - 1];
    }
    arr[airCleaner[0]][2] = 0;
}

void operateBottomAirCleaner() {
    // 시계 방향으로 회전;
    for (int i = airCleaner[1] + 1; i < r; i++) {
        arr[i][1] = arr[i + 1][1];
    }

    for (int i = 1; i < c; i++) {
        arr[r][i] = arr[r][i + 1];
    }

    for (int i = r; i > airCleaner[1]; i--) {
        arr[i][c] = arr[i - 1][c];
    }

    for (int i = c; i > 2; i--) {
        arr[airCleaner[1]][i] = arr[airCleaner[1]][i - 1];
    }
    arr[airCleaner[1]][2] = 0;
}

void operateAirCleaner() {
    operateTopAirCleaner();
    operateBottomAirCleaner();
}

int accumulateDust() {
    int ssum = 0;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            if (arr[i][j] == -1)
                continue;
            ssum += arr[i][j];
        }
    }
    return ssum;
}

int main() {
    cin >> r >> c >> t;
    arr.assign(r + 1, vector<int>(c + 1, 0));

    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == -1) {
                airCleaner.push_back(i);
            }
        }
    }

    while (t--) {
        extendsDust();       // 1. 미세먼지 확장
        operateAirCleaner(); // 2. 공기청정기 작동
    }

    // 3. 전체에 남아있는 미세먼지 양 구하여 출력
    cout << accumulateDust();

    return 0;
}