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

백준의 미세먼지 안녕(17144) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 이 문제에서는 구현해야 할 것이 크게 2개가 있다. 먼지가 확산하는 과정과 공기청정기에 의해서 먼지가 움직여지는 과정

   이렇게 크게 2과정이 있다. 각각의 과정대로 어떻게 구현했는지 알아보도록 하자.

   먼저 먼지가 확산하는 과정이다. 먼지가 확산할 때에는 가장 중요한 것이 인접한 정점에 숫자들이 붙어 있는 경우를 어떻게

   처리할지가 가장 중요하다고 생각한다. 왜냐하면 한 정점을 기준으로 동서남북 4방향으로 모두 값이 없다면 그냥 먼지를

   번식시켜 주면 되지만, 어느 한 방향이라도 값이 있다면 이 다음에 정점을 탐색할 때 영향을 미치기 때문이다.

   본인이 무슨 소리를 하고 싶은건지 그림으로 한번 이해해보자.

  

   먼지가 다음과 같이 번식되어 있다고 생각해보자. 먼저 먼지의 양이 20인 (1, 1)을 한번 봐보자.

   저 경우에는 인접한 4방향 모두 먼지가 존재하지 않는다. 즉, 그냥 번식을 시켜주면 된다. 번식시켜준다면 다음과 같이 될

   것 이다.

  

    뭐 여기까지는 어려운 부분이 없을 것이다. 물론 위의 그림에서 공기청정기는 생략한 것이다. 실제 문제에서는 공기청정기

    의 위치까지 모두 고려해주어야 한다. 단지, 먼지의 확장하는 과정을 쉽게 설명하기 위해서 공기청정기를 생략하였다.

    그렇다면 25가 존재하는 (2, 2) 좌표와 30이 존재하는 (2, 3)좌표를 한번 봐보도록 하자. 우리가 일반적으로 2중 for문으로

    맵을 탐색한다면, 아마 (2, 2)인 25부터 탐색을 하고 그 다음번에 (2, 3)에 존재하는 30을 탐색하게 될 것이다.

    그렇다면 25인 (2,2)부터 먼지 번식을 한번 시켜보자.

    25 / 5 = 5 이고, 5가 4방향으로 퍼지게 되면, 다음과 같이 될 것이다.

   

   여기까지는 괜찮다. 기존의 (1, 1)에 의해서 번식된 (1, 2)에 존재했던 먼지의 양인 4도 +5가 될 것이고 동서남북이 모두

    + 5씩 될 것이다. 하지만 ! (2, 3)에 존재했던 30에 값에 주목해보자. 30은 30인채로 먼지를 확장해야 한다.

    즉, 25에 의해서 먼지의 양이 35가 되고, 35라는 데이터에 대해서 확장을 시키면 안된다는 것이다.

    여기서 우리는 확장을 시키더라도 값을 그때그때 변경하면 안되고 저장만 해 주었다가 한번에 변경해줘야 한다는 것을

    눈치챌 수 있다. 그렇다면 어떻게 어디다가 저장을 해줄까??

    본인은 이 부분을 위해서 C_MAP 이라는 원본 MAP의 복사형태를 하나 더 만들어 주었다.

    구현과정은 이렇다. 모든 계산은 MAP을 기준으로 한다. MAP에 숫자가 있으면 번식을 시키는 것이고 없으면 번식을

    시키지 않는다. 하지만 이 때, 번식을 하더라도 MAP에 있는 숫자에는 변화를 주지 않는다. 모든 값은 C_MAP이라는

    임시적으로 사용하는 복사된 맵에다가만 저장을 해준다.

    그렇다면 위의 과정을 복사된 맵에다가 저장해준다고 생각하고 먼지를 확산 시키면 어떻게 될까??

    중간 과정에서 원래의 맵에서 값이 변화되는 일이 없어질 것이다. 즉, 위의 그림처럼 (2, 3)에 있는 30이라는 값이 30 + 5가

    되는 일이 원본맵에서는 일어나지 않는다는 것이다. 단지, 복사된 맵에서 일어날 뿐 !

    이 후, 모든 번식을 마쳤으면 복사된 맵을 다시 원본 맵으로 옮겨주기만 하면 된다.

    즉, 간략하게 순서를 나타내보자면 다음과 같다.

    1. 원본의 맵을 임의의 복사된 맵으로 옮겨주기

    2. 복사된 맵에서 모든 먼지 확장시키기. 확장시킬 때 기준이 되는 값은 원본의 맵.

    3. 복사된 맵을 다시 원본 맵으로 옮겨주기.

    본인이 사용한 본문 코드에서 함수 (void Dust_Expansion()) 이 이 함수이니 참고하도록 하자.

2. 두 번째 과정은 공기청정기에 의해서 먼지들이 움직이는 과정이다. 본인은 이 부분을 그냥 4개의 for문을 이용해서

   옮겨주었다. 이 부분에서는 특별한 알고리즘이 사용된 것이 아니기 때문에 별다른 설명은 생략하도록 하겠다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int R, C, T, Answer;
int MAP[MAX][MAX];
int C_MAP[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
pair<int, int> Air_Cleaner[2];
 
void Input()
{
    cin >> R >> C >> T;
    int Idx = 0;
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == -1)
            {
                Air_Cleaner[Idx].first = i;
                Air_Cleaner[Idx].second = j;
                Idx++;
            }
        }
    }
}
 
void Print()
{
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            if (MAP[i][j] == -1) cout << "- ";
            else cout << MAP[i][j] << " ";
        }
        cout << endl;
    }
    cout << "######################################################" << endl;
}
 
void Copy_MAP(int A[][MAX], int B[][MAX])
{
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            A[i][j] = B[i][j];
        }
    }
}
 
void Dust_Expansion()
{
    Copy_MAP(C_MAP, MAP);
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            if (MAP[i][j] != 0 && MAP[i][j] != -1)
            {
                int Cnt = 0;
                int Value = MAP[i][j] / 5;
                for (int k = 0; k < 4; k++)
                {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
 
                    if (nx >= 0 && ny >= 0 && nx < R && ny < C)
                    {
                        if (MAP[nx][ny] != -1)
                        {
                            C_MAP[nx][ny] = C_MAP[nx][ny] + Value;
                            Cnt++;
                        }
                    }
                }
                C_MAP[i][j] = C_MAP[i][j] - (Cnt * Value);
            }
        }
    }
    Copy_MAP(MAP, C_MAP);
}
 
void Move_Dust()
{
    for (int Idx = 0; Idx < 2; Idx++)
    {
        if (Idx == 0)
        {
            // 1. 공기청정기 위에서부터 (0, 0)까지 모든 값 떙겨주기
            for (int i = Air_Cleaner[Idx].first - 1; i > 0; i--)
            {
                MAP[i][0] = MAP[i - 1][0];
            }
            // 2. 가장 윗줄 땡겨주기
            for (int i = 0; i < C - 1; i++)
            {
                MAP[0][i] = MAP[0][i + 1];
            }
            // 3. 반대편 세로라인 땡겨주기
            for (int i = 1; i <= Air_Cleaner[Idx].first; i++)
            {
                MAP[i - 1][C - 1] = MAP[i][C - 1];
            }
            // 4. 공기청정기 라인 땡겨주기
            for (int i = C - 1; i > 1; i--)
            {
                MAP[Air_Cleaner[Idx].first][i] = MAP[Air_Cleaner[Idx].first][i - 1];
            }
            MAP[Air_Cleaner[Idx].first][1] = 0;
        }
        else
        {
            for (int i = Air_Cleaner[Idx].first + 1; i < R - 1; i++)
            {
                MAP[i][0] = MAP[i + 1][0];
            }
            for (int i = 0; i < C - 1; i++)
            {
                MAP[R - 1][i] = MAP[R - 1][i + 1];
            }
            for (int i = R - 1; i >= Air_Cleaner[Idx].first; i--)
            {
                MAP[i][C - 1] = MAP[i - 1][C - 1];
            }
            for (int i = C - 1; i > 1; i--)
            {
                MAP[Air_Cleaner[Idx].first][i] = MAP[Air_Cleaner[Idx].first][i - 1];
            }
            MAP[Air_Cleaner[Idx].first][1] = 0;
        }
    }
}
 
int Count_Dust()
{
    int Sum = 0;
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            if (MAP[i][j] == -1) continue;
            Sum = Sum + MAP[i][j];
        }
    }
    return Sum;
}
 
void Solution()
{
    for (int i = 0; i < T; i++)
    {
        Dust_Expansion();
        Move_Dust();
    }
    
    Answer = Count_Dust();
}
 
void Solve()
{
    Input();
    Solution();
    cout << Answer << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}