[ SWEA 1907 ] 모래성 쌓기 (C++)

SWExpertAcademy의 모래성 쌓기(1907 / D5) 문제이다.

[ 문제풀이 ]

파도에 의해서 모래성이 부서질 때, 파도가 몇 번 쳐야 더 이상 변하지 않는 모래성의 형태가 될 수 있는지 구하는 문제이다.

먼저, 가장 간단하게 생각해볼 수 있는건 모든 맵을 탐색하면서 파도가 한번 칠 때 마다 그 파도에 의해서 부서지는 모래성을 표시해주는 과정을 더 이상 모래성의 형태가 변하지 않을 때 까지 반복하는 것이다.

하지만, 맵의 크기가 꽤나 큰 편 이라서 파도가 칠 때 마다 모든 맵을 탐색하는 것은 시간초과를 받을 수 있다.

따라서 파도가 칠 때 마다 매번 모든 맵을 탐색하지 않는 다른 방법을 생각해봐야 한다.

본인은 모래성이 아닌, 모래를 기준으로 접근해 보았다.

문제에서 [ 예제풀이 ] 로 적혀있는 맵을 그대로 가져온 것이다.

가장 첫 파도에 의해서 빨강색으로 표시된 모래성들이 파랑색으로 표시된 모래들 때문에 무너지게 된다.

그럼 여기서부터 생각을 한번 해보자. 과연 그 다음에 무너지는 모래성들은 어떤 모래들에 영향을 받게될까 ?

먼저 결과부터 그 다음 무너지는 모래성을 표시하면 다음과 같다.

그 다음 파도에 의해서는 빨강색으로 표시된 '2'가, 파랑색 모래들에 의해서 무너지게 될 것이다.

지금 보게 되면, 빨강색으로 표시된 '2'는 그 전에 무너져버린 우측 하단에 있는 '3'에 영향을 받게 된다.

즉, "현재 턴에서 무너져버리는 모래성은 다음 턴에 무너져버릴 모래성에 영향을 미치게 된다." 라는 것이다.

위에서 한 단계를 더 나아가보자. 이번 턴에서는 빨강색 '2'가 무너져 버릴 것이다. 그럼 무너져버린 빨강색'2'는 누구한테

영향을 미치게 될까 ?? 그 다음 무너져버릴 '4'에 영향을 미치게 된다.

이렇게 빨강색 '4'는 상하좌우에 있는 파랑색 모래들에 의해서 무너져 버리게 될 것이다.

그럼 지금까지 이 이야기를 왜 했는지 다시 생각해보자. 맵을 다 탐색하면 안된다~ 라는 식의 이야기를 하다가 여기까지

와버렸다. 그런데 위의 과정만 본다면, 매번 파도가 칠 때 마다 모래가 있는 좌표들을 다 탐색해보면서 모래성을

무너뜨리는 것 아닌가 라는 생각을 할 수도 있다.

하지만 항상 모든 모래들의 좌표들을 다 탐색하지 않았다. 왜냐하면 모래성들의 값들을 매 턴마다 주변에 있는 모래의 수 만큼

체력(?)을 깍아놨기 때문이다.

다시 처음으로 돌아가보자.

입력과 동시에 모래들의 좌표들을 Queue에 저장해 주었다. 그럼 현재 Queue에는 아래 표시된 칸들이 들어가져 있을 것이다.

그리고, 이 모래들을 하나하나 다 탐색해보면서 주변에 숫자가 있다면 그 숫자의 값을 -- 시켜주는 것이다.

즉, 저 모래들의 탐색이 다 끝나면 맵은 사실상 아래와 같은 형태일 것이다.

이 때 ! 0이 되는 좌표가 중요하다. 0이 된다 라는 것은 모래성이 무너졌다 라는 것을 의미하고 위에서도 말했듯이,

이번턴에서 무너지는 모래성은 다음턴에 무너질 모래성에 영향을 미치는 모래가 되어버리게 된다.

따라서, 0이 된 좌표들에 대해서만 Queue에 넣어주었다.

즉, 한 턴이 끝나고 나면 Queue에 들어가져 있는 좌표들은 다음과 같을 것이다.

이 좌표들만 들어가져 있을 것이다. 그 이후에 그럼 탐색을 계속 해보자.

마찬가지로 모래 주변에 있는 숫자들을 하나씩 깍아보면 위와 같은 상태가 될 것이다.

그 과정에서 역시나 0이 되어버린 좌표가 발생했고 0이 된 좌표만 Queue에 넣어주었다.

한번만 더 그 과정을 진행해보자.

왼쪽에 있는 파랑색 점에 의해서 0이 되는 값이 발생해 버렸고, 0이된 지점만 Queue에 들어가져 있을 것이다.

그럼 오른쪽 그림에서 한번 더 진행하게 되면 ? 아무런 값도 Queue에 들어가지지 않을 것이다.

왜 ? 주변에 숫자가 없기 때문에 ! 숫자가 있다고 하더라도 0이된 값이 없기 때문에 들어가지지 않을 것이다.

이렇게 되면 더 이상 형태가 변하지 않는 다는 것을 의미한다.

이런 방법을 이용해서 본인은 매번 파도가 칠 때 마다 맵 전체를 탐색하는 과정을 없애주었다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
 
#define MAX 1010
#define endl "\n"
using namespace std;
 
int N, M, Answer;
int MAP[MAX][MAX];
queue<pair<int, int>> Q;
 
int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
 
void Initialize()
{
    Answer = 0;
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            char C; cin >> C;
            if (C != '.') MAP[i][j] = C - '0';
            else Q.push(make_pair(i, j));
        }
    }
}
 
void BFS()
{
    int Size = Q.size();
    while (Size--)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 8; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)
            {
                if (MAP[nx][ny] != 0)
                {
                    MAP[nx][ny]--;
                    if (MAP[nx][ny] == 0) Q.push(make_pair(nx, ny));
                }
            }
        }
    }
}
 
void Solution()
{
    while (1)
    {
        BFS();
        int Size = Q.size();
        if (Size == 0) break;
        Answer++;
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}