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

문제링크 : https://www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int R, C, T, result = 0;
int arr[50][50]; //기존 배열
int arr_changed[50][50]; //변동된 배열
int dr[] = {1, -1, 0, 0};
int dc[] = {0, 0, 1, -1};
vector<int> air_idx;

void clean()
{
    //air_idx[0] -> 윗쪽 (반시계 방향)
    for(int i = air_idx[0]-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=1; i<=air_idx[0]; i++) //↑
    {
        arr[i-1][C-1] = arr[i][C-1];
    }

    for(int i=C-1; i>1; i--) //→
    {
        arr[air_idx[0]][i] = arr[air_idx[0]][i-1];
    }

    arr[air_idx[0]][1] = 0; //공기청정기 옆칸은 불어서 없어짐

    //air_idx[1] -> 아래쪽 (시계 방향)
    for(int i = air_idx[1] + 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>=air_idx[1]; i--) //↓
    {
        arr[i][C-1] = arr[i-1][C-1];
    } 

    for(int i=C-1; i>1; i--) //→
    {
        arr[air_idx[1]][i] = arr[air_idx[1]][i-1];
    }

    arr[air_idx[1]][1] = 0; //공기청정기 옆칸은 불어서 없어짐

}

void spread()
{
    for(int i=0; i<R; i++)
    {
        for(int j=0; j<C; j++)
        {
            int cnt = 0;
            int spread_value = arr[i][j]/5;
            if (arr[i][j] == 0 || arr[i][j] == -1) continue; //먼지가 없거나 공기청정기라면

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

                if(nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                if(arr[nr][nc] == -1) continue; //공기청정기라면
                arr_changed[nr][nc] += spread_value; //더해줌
                cnt++; //확산 갯수 증가
            }
            arr_changed[i][j] -= cnt * spread_value; //원래값은 확산된 만큼 빼줌
        }
    }

    for(int i=0; i<R; i++)
    {
        for(int j=0; j<C; j++)
        {
            arr[i][j] += arr_changed[i][j];  //변동된 값 적용
            arr_changed[i][j] = 0;           //변동용 배열 초기화
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> R >> C >> T;

    for(int i=0; i<R; i++)
    {
        for(int j=0; j<C; j++)
        {
            cin >> arr[i][j];
            if(arr[i][j] == - 1)
            {
                air_idx.push_back(i);
            }
        }
    }

    while(T--)
    {
        spread();
        clean();
    }

    for(int i=0; i<R; i++)
    {
        for(int j=0; j<C; j++)
        {
            if(arr[i][j] == -1) continue; //공기청정기는 패스
            result += arr[i][j];
        }
    }
    cout << result << "\n";
    
    return 0;

}

상당한 노가다가 포함된 구현 문제이다.

기존 배열과 변동된 미세먼지를 저장할 배열이 필요하다.

4방향을 탐색하면서 확산되고 줄어든 미세먼지를 저장하고, 이를 기존 배열에 더해줌으로서 업데이트 해준다.

업데이트 해준후 변동용 배열을 초기화해주는 것을 잊으면 안된다.

 

미세먼지 위치 변경은 반복문으로 일일히 적어주었다.

여기서 주의할것은 방향 순서가 잘못될 경우 잘못된 값이 밀려서 오답이 나올 수도 있다.

그리고 공기청정기 옆칸은 따로 0을 넣어주어야 한다.

기존에 있던 값은 밀어서 없어지는데, 해당 값은 바로 옆이 공기청정기라서 밀어져서 오는 값이 없기 때문에 따로 0으로 넣어서 처리해줘야 한다.