[백준 17144][구현] 미세먼지 안녕!

문제 설명

문제 링크

 

집은 격자판 (R*C)로 나타낸다. 로봇청소기는 항상 첫 번째 열에만 위치하고, 두 개의 행을 차지한다. 다시 말해, (2*1)의 크기이다. 

 

또 각 칸에 있는, 0초 시점의 미세먼지가 주어진다. 미세먼지는 확산 가능한데, 이는 매초마다 이뤄지며 동시에 일어난다. (r,c)에 있는 미세먼지는 인접한 네 방향으로 확산되고, 인접한 방향이 공기청정기나 벽으로 막혀있다면 확산이 발생하지 않는다. 확산되는 양은 A(r,c)/5이고 소수점은 버린다. (r,c)에 남은 양은 기존 미세먼지 양에 확산된 총량을 제한 크기이다.

 

미세먼지가 확산되고 나서, 공기청정기가 작동한다. 공기청정기에서는 바람이 나오는데, 위쪽 공기청정기는 반시계 방향, 아래쪽 공기청정기는 시계방향으로 순환한다. 바람의 방향대로 미세먼지가 이동하며, 공기청정기에 들어간 미세먼지는 정화된다.

 

T초가 지난 후 방에 남아있는 미세먼지의 양을 구하는 문제이다.

 

 

문제 풀이

삼성 코딩테스트 기출 문제인 만큼, 역시나 최적화보단 구현 및 예외 찾기에 집중해야한다.

 

문제를 함수 단위로 쪼개면, 크게 미세먼지 확산 / 공기청정기 작동 으로 쪼갤 수 있다.

 

미세먼지 확산에서 주의할 점은, 확산이 동시에 일어난다. 당연하게도 코드에서는 동시에 발생시킬 수 없으므로 예외처리를 해줘야하는데, 예를 들어 위에서부터 아래로 연산을 진행할 때 위에서 발생한 확산이 아래에서 발생하는 확산에 영향을 주어선 안된다. 예를 들어, (0,2)에서 확산이 발생해 (1,2)의 미세먼지 양이 많아졌다고 하자. 이 때 (1,2)칸의 미세먼지 확산을 위한 연산을 수행(5 나누기)할 때 (0,2)으로부터 확산된 미세먼지 양은 고려되선 안된다. 본인은 임시 배열을 만듦으로 해결하였다.

 

공기청정기 작동은 다시 위쪽 공기청정기와 아래쪽 공기청정기로 나누었다. (이전에 비슷한 장르로 출제를 해봤던 만큼) 딱히 예외는 발생하지 않았다. 방향이 헷갈리기 쉬우므로 역시 종이 등에 그리면서 풀이해보자.

 

 

코드

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


int r, c, t, arr[50][50];                           // 입력값
pair<int, int> top[4], bottom[4];                   // 공기청정기 방향                                     // 미세먼지 총량
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // 확산방향
int tmp_arr[50][50];                                // 일괄적용 임시 저장소

void expansion(int x, int y)
{
    for (int i = 0; i < 4; ++i)
    {
        int dx = x + dir[i][0], dy = y + dir[i][1];

        if (dx < 0 || dy < 0 || dx >= r || dy >= c // 범위 초과
            || arr[dx][dy] == -1                   // 공기청정기
        )
            continue;
        tmp_arr[dx][dy] += arr[x][y] / 5;
        tmp_arr[x][y] -= arr[x][y] / 5;
    }
}

void all_expansion()
{
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            if (arr[i][j] > 0)
            {
                expansion(i, j);
            }
        }
    }
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            arr[i][j] += tmp_arr[i][j];
            tmp_arr[i][j] = 0;
        }
    }
}

void wind_top()
{
    pair<int, int> ld = top[0], rd = top[1], rt = top[2], lt = top[3];

    arr[ld.first - 1][ld.second] = 0; // 미세먼지 제거
    // 좌측상단 -> 좌측하단 이동
    for (int i = ld.first - 1; i > 0; --i)
    {
        arr[i][0] = arr[i - 1][0];
    }
    // 우측상단 -> 좌측상단 이동
    for (int i = 0; i < c - 1; ++i)
    {
        arr[0][i] = arr[0][i + 1];
    }
    // 우측하단 -> 우측상단 이동
    for (int i = 0; i < ld.first; ++i)
    {
        arr[i][c - 1] = arr[i + 1][c - 1];
    }
    // 좌측하단 -> 우측하단 이동
    for (int i = c - 1; i > 1; --i)
    {
        arr[ld.first][i] = arr[ld.first][i - 1];
    }
    arr[ld.first][1] = 0;
}

void wind_bot()
{
    pair<int, int> lt = bottom[0], rt = bottom[1], rd = bottom[2], ld = bottom[3];

    arr[lt.first + 1][0] = 0; // 미세먼지 제거
    // 좌측하단 -> 좌측상단 이동
    for (int i = lt.first + 1; i < r - 1; ++i)
        arr[i][0] = arr[i + 1][0];

    // 우측하단 -> 좌측하단 이동
    for (int i = 0; i < c - 1; ++i)
        arr[r - 1][i] = arr[r - 1][i + 1];

    // 우측상단 -> 우측하단 이동
    for (int i = r - 1; i > rt.first; --i)
        arr[i][c - 1] = arr[i - 1][c - 1];

    // 좌측상단 -> 우측상단 이동
    for (int i = c - 1; i > 1; --i)
        arr[lt.first][i] = arr[lt.first][i - 1];

    arr[lt.first][1] = 0;
}

int arr_sum()
{
    // 총량 계산
    int sum = 0;
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            if (arr[i][j] != -1)
            {
                sum += arr[i][j];
            }
        }
    }
    return sum;
}

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

    cin >> r >> c >> t;
    bool top_switch = true;
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            cin >> arr[i][j];
            if (arr[i][j] == -1)
            {
                if (top_switch)
                {
                    top_switch = false;
                    top[0] = {i, j};
                    top[1] = {i, c - 1};
                    top[2] = {0, c - 1};
                    top[3] = {0, 0};
                }
                else
                {
                    bottom[0] = {i, j};
                    bottom[1] = {i, c - 1};
                    bottom[2] = {r - 1, c - 1};
                    bottom[3] = {r - 1, 0};
                }
            }
        }
    }

    // t초동안 실행
    while (t--)
    {
        // getchar();
        // print();
        all_expansion();
        // print();
        wind_top();
        wind_bot();
        //  cout << arr_sum() << '\n';
    }

    cout << arr_sum() << '\n';
}