[Algorithm] Baekjoon 20058번 : 마법사 상어와 파이어스톰

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

20058번: 마법사 상어와 파이어스톰

using namespace std;
 
int n, q;
int arr[64][64] = { 0 };
int temp[64][64] = { 0 };
int lSize[1001] = { 0 };
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
 
int sumIce = 0;
int maxSize = 0;
bool visited[64][64] = { false };
 
void rotate(int startY, int startX, int l)
{
    int size = pow(2, l);
 
    for (int i = 0; i < size; ++i)
    {
        for (int j = 0; j < size; ++j)
        {
            temp[j][size - i - 1] = arr[i + startY][j + startX];
        }
    }
 
    for (int i = 0; i < size; ++i)
    {
        for (int j = 0; j < size; ++j)
        {
            arr[i + startY][j + startX] = temp[i][j];
        }
    }
}
 
void melt()
{
    memcpy(temp, arr, sizeof(temp));
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (temp[i][j] == 0) continue;
 
            int count = 0;
 
            for (int d = 0; d < 4; ++d)
            {
                int nextY = i + dir[d][0];
                int nextX = j + dir[d][1];
 
                if (nextY < 0 || nextY >= n) continue;
                if (nextX < 0 || nextX >= n) continue;
 
                if (temp[nextY][nextX] >= 1) ++count;
            }
 
            if (count < 3) arr[i][j] = max(0, --arr[i][j]);
        }
    }
}
 
void GetSumIce()
{
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            sumIce += arr[i][j];
        }
    }
}
 
struct Node
{
    int y;
    int x;
};
 
void GetMaxSize(int startY, int startX)
{
    int count = 0;
 
    queue<Node> q;
    q.push({ startY,startX });
    ++count;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= n) continue;
            if (nextX < 0 || nextX >= n) continue;
            if (visited[nextY][nextX]) continue;
            if (arr[nextY][nextX] == 0) continue;
 
            visited[nextY][nextX] = true;
            q.push({ nextY,nextX });
            ++count;
        }
    }
 
    maxSize = max(maxSize, count);
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> q;
 
    n = pow(2, n);
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 0; i < q; ++i)
    {
        cin >> lSize[i];
 
        int size = pow(2, lSize[i]);
 
        for (int r = 0; r < n; r += size)
        {
            for (int c = 0; c < n; c += size)
            {
                rotate(r, c, lSize[i]);
            }
        }
 
        melt();
    }
 
    GetSumIce();
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (visited[i][j]) continue;
            if (arr[i][j] == 0) continue;
 
            visited[i][j] = true;
            GetMaxSize(i, j);
        }
    }
 
    cout << sumIce << endl << maxSize;
}

 

행렬회전하는 코드 말고는 일방적인 구현문제이다.

다만 유의할 점은, 얼음을 녹일 때 반드시 원본기준으로 녹여야한다는것을 잊으면 안된다.

이전에 녹인게 다음거에 영향을 줘서는 안된다.

 

행렬회전코드같은 경우는, 원본의 회전시킬 범위내의 코드를 temp의 0부터 시작하는 같은범위로 회전시켜서 복사한다. 

이후 전부 회전복사 후, 다시 원본의 범위로 그대로 복사했다.