[ 삼성 SW역량 평가 17144 ] 미세먼지 안녕! (C++)

[ 난이도 ]

★☆☆

 

[ 문제 링크 ]

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

 

[ 문제 풀이 ]

해당 문제를 풀기 위해

1. 매초마다 가능한 방향만큼 cnt를 해주어 값을 빼주었다.

2. 그리고 더해저야할 값은 Wide_Map에 저장하여 한번에 더해주었다.

이렇게 한 이유는 각칸마다 매번 값을 확산시키면 다음칸의 값이 변하게되어 결과에 영향을 미치게 되기 때문이다.

3. 그리고 확산이 완료되면 방향을 이동시킨다.

 

[ 소스 코드 ]

// 헤더파일을 불러옵니다.
#include <iostream>
#include <vector>
using namespace std;
 
// 맵의 최대 크기는 50 입니다.
#define Max_Size 51
 
// A : 미세먼지 수, Wide_Map : 얼마나 확산될지 값을 저장하는 맵
int A[Max_Size][Max_Size];
int Wide_Map[Max_Size][Max_Size] = { 0 };
 
// R: 행, C: 열, T: 시간
int R, C, T;
 
// 각각 동서남북임.
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
 
// 미세먼지 청소기의 좌표를 받아옴.
vector<int> Cleaner;
 
// 입력을 받아오는 함수
void Load_Input()
{
    cin >> R >> C >> T;
    for (int i = 1; i <= R; ++i)
    {
        for (int j = 1; j <= C; ++j)
        {
            cin >> A[i][j];
            if (A[i][j] == -1) Cleaner.push_back(i);
        }
    }
}
 
// 현재 맵에 있는 미세먼지의 합을 구하는 함수.
int Answer()
{
    int sum = 0;
    for (int i = 1; i <= R; ++i)
    {
        for (int j = 1; j <= C; ++j)
        {
            if (A[i][j] == -1) continue;
            sum = sum + A[i][j];
        }
    }
    return sum;
}
 
// 어느 칸에 얼만큼 확산될지 결정해주는 지도를 만들어주는 함수
void Make_Wide_Map()
{
    // 모든 행
    for (int i = 1; i <= R; ++i)
    {
        // 모든 열에 대해서
        for (int j = 1; j <= C; ++j)
        {
            // 해당칸의 값을 5로 나눠주고
            int cnt = 0;
            int dust = A[i][j] / 5;
 
            // 동서남북 탐색하여 조건이 되는 경우 확산지도에 넣어준다.
            for (int k = 0; k < 4; ++k)
            {
                int x = i;
                int y = j;
 
                int nx = x + dx[k];
                int ny = y + dy[k];
 
                if (nx <1 || nx > R || ny < 1 || ny > C) continue;
                if ((nx == Cleaner.at(0) && ny == 1) || (nx == Cleaner.at(1) && ny == 1)) continue;
                Wide_Map[nx][ny] += dust;
                cnt++;
            }
            // 동서남북중 된 방향을 cnt하여 뺴준다.
            A[i][j] = A[i][j] - cnt * dust;
        }
    }
}
 
// 만들어진 확산지도를 각 칸에 더해주는 함수
void Put_Wide_Map()
{
    for (int i = 1; i <= R; ++i)
    {
        for (int j = 1; j <= C; ++j)
        {
            A[i][j] = A[i][j] + Wide_Map[i][j];
        }
 
    }
}
 
// 매 확산마다 확산지도를 초기화시켜줌.
void Reset_Wide_Map()
{
    for (int i = 1; i <= R; ++i)
    {
        for (int j = 1; j <= C; ++j)
        {
            Wide_Map[i][j] = 0;
        }
 
    }
}
 
void Operate_Cleaner()
{    
    // 청정기의 좌표를 받아옴. 열은 고정이므로 x좌표만 가져옴.
    int Cleaner_x1 = Cleaner.at(0);
    int Cleaner_x2 = Cleaner.at(1);
 
    // 윗방향 각각 →↑←↓임
    for (int z = Cleaner_x1 - 1; z > 1; --z) A[z][1] = A[z - 1][1];
    for (int k = 1; k < C; ++k) A[1][k] = A[1][k + 1];
    for (int j = 1; j < Cleaner_x1; ++j) A[j][C] = A[j + 1][C];
    for (int i = C; i >= 3; --i) A[Cleaner_x1][i] = A[Cleaner_x1][i - 1];
    A[Cleaner_x1][2] = 0;
 
    // 밑방향 각각 →↓←↑임
    for (int z = Cleaner_x2 + 1; z < R; ++z) A[z][1] = A[z + 1][1];
    for (int k = 1; k < C; ++k) A[R][k] = A[R][k + 1];
    for (int j = R; j > Cleaner_x2; --j) A[j][C] = A[j - 1][C];
    for (int i = C; i >= 3; --i) A[Cleaner_x2][i] = A[Cleaner_x2][i - 1];
    A[Cleaner_x2][2] = 0;
}
 
// 1초에 1번이므로 T번만큼 반복하며 정답을 산출하는 함수.
void Solve()
{
    for (int i = 0; i < T; ++i)
    {
        Make_Wide_Map();
        Put_Wide_Map();
        Reset_Wide_Map();
        Operate_Cleaner();
    }
    cout << Answer();
}
 
int main()
{
    // 입력을 받아옵니다.
    Load_Input();
    // 문제를 해결합니다.
    Solve();
    return 0;
}