백준 21610번 문제 풀이 (오랜만 ㅎㅎ)

문제 설명

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 N×N인 격자에서 연습하려고 한다. 격자의 각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고, A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다.

격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는 1번 행이, 1번 행의 위에는 N번 행이 있고, 1번 열의 왼쪽에는 N번 열이, N번 열의 오른쪽에는 1번 열이 있다.

비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다. 구름은 칸 전체를 차지한다. 이제 구름에 이동을 M번 명령하려고 한다. i번째 이동 명령은 방향 di과 거리 si로 이루어져 있다. 방향은 총 8개의 방향이 있으며, 8개의 정수로 표현한다. 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 이동을 명령하면 다음이 순서대로 진행된다.

1. 모든 구름이 di 방향으로 si칸 이동한다.
2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
3. 구름이 모두 사라진다.
4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
   • 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
   • 예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.
5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.

문제를 보고 든 생각

• 삼성 기출 문제가 항상 그렇듯 함수를 잘 쪼개야 겠다는 생각을 했다.
• 함수만 잘 쪼개도 문제는 풀린다!

풀이 간단 설명

1. 구름이 있는 곳을 위한 변수 cloud, 이동한 후 구름의 위치를 저장한 변수 cloudClone 두 개를 사용했다.
2. 바운드 체크도 열심히 했다.
3. 구름이 있던던 곳은 queue를 이용해서 저장한 다음 체크했다.
4. 함수 설명
   • initA(): 가장 초기 A 배열을 초기화 하는 함수
   • checkCloud(): 처음 주문을 외운다면 [N,1][N,2][N-1,1][N-1,2]에 구름을 만들고 아니라면
     a. 구름이 없고 물이 2이상인 곳에 구름 생성
     b. 구름이 있었다면 구름 생성 안함!
     c. 패스
   • copyMovedCloneCloud2Cloud(int &d, int &sn, int &sm): d방향으로 sn, sm만큼 움직인 후 cloneCloud에 복사
   • checkWhereRained(): 어디에 비가 내렸었는지 queue를 이용해서 저장
   • waterCopyBug(): 비가 내린 곳 기준 대각선으로 물이 있나 확인하고 물 있는 만큼 물 양 증가
   • moveCloud(): 구름 이동 함수
   • rain(): 비 내리게 함
   • countAWater(): 물 양 세는 함수

코드

#include <iostream>
#include <queue>

#define MAX_N 50

typedef long long ll;

using namespace std;

int dir[9][2] = {{0, 0}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}};
int diagD[4][2] = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}};
ll A[MAX_N+1][MAX_N+1];
bool cloud[MAX_N+1][MAX_N+1];
bool cloneCloud[MAX_N+1][MAX_N+1];
ll N, M;
bool spellCalled = false;
struct strt
{
    int r, c;
};
queue<strt> q;

void initA()
{
    cin >> N >> M;
    for(int r=1; r<=N; ++r)
    {
        for(int c=1; c<=N; ++c)
        {
            ll val; cin >> val;
            A[r][c] = val;
        }
    }
}

void checkCloud()
{
    if(!spellCalled)
    {
        cloud[N][1] = true;
        cloud[N][2] = true;
        cloud[N-1][1] = true;
        cloud[N-1][2] = true;
        spellCalled = true;
    }
    else
    {
        for(int r=1; r<=N; ++r)
        {
            for(int c=1; c<=N; ++c)
            {
                if(!cloneCloud[r][c] && A[r][c] >= 2)
                {
                    cloud[r][c] = true;
                    A[r][c] -= 2;
                }
                else if(cloneCloud[r][c])
                {
                    cloud[r][c] = false;
                }
                else
                {
                    cloud[r][c] = cloneCloud[r][c];               
                }
            }
        }
    }
}

void clearCloneCloud()
{
    for(int r=1; r<=N; ++r)
    {
        for(int c=1; c<=N; ++c)
        {
            cloneCloud[r][c] = false;
        }
    }
}

void boundCheckNextRC(int &nr, int &nc)
{
    if(nr > N)
    {
        nr -= N;
    }
    if(nc > N)
    {
        nc -= N;
    }
    if(nr <= 0)
    {
        nr += N;
    }
    if(nc <= 0)
    {
        nc += N;
    }
}

void copyMovedCloneCloud2Cloud(int &d, int &sn, int &sm)
{
    for(int r=1; r<=N; ++r)
    {
        for(int c=1; c<=N; ++c)
        {
            if(!cloud[r][c])
            {
                continue;
            }
            int nr = r + dir[d][0]*sn;
            int nc = c + dir[d][1]*sm;
            boundCheckNextRC(nr, nc);
            cloneCloud[nr][nc] = true;
        }
    }
}

void checkWhereRained()
{
    for(int r=1; r<=N; ++r)
    {
        for(int c=1; c<=N; ++c)
        {
            if(!cloneCloud[r][c])
            {
                continue;
            }
            q.push({r, c});
        }
    }
}

void waterCopyBug()
{
    while(!q.empty())
    {
        int r = q.front().r, c = q.front().c;
        q.pop();

        for(int i=0; i<4; ++i)
        {
            int nr = r + diagD[i][0], nc = c + diagD[i][1];
            if(nr <= 0 || nc <= 0 || nr > N || nc > N)
            {
                continue;
            }
            if(A[nr][nc] > 0)
            {
                ++A[r][c];
            }
        }
    }
}

void moveCloud()
{
    int d, s; cin >> d >> s;
    int sn = s%N, sm = s%N;
    clearCloneCloud();
    copyMovedCloneCloud2Cloud(d, sn, sm);
}

void rain()
{
    for(int r=1; r<=N; ++r)
    {
        for(int c=1; c<=N; ++c)
        {
            if(!cloneCloud[r][c])
            {
                continue;
            }
            ++A[r][c];
        }
    }
}

void spellStart()
{
    checkCloud();
    moveCloud();
    rain();
    checkWhereRained();
    waterCopyBug();
}

void countAWater()
{
    ll cnt = 0;
    for(int r=1; r<=N; ++r)
    {
        for(int c=1; c<=N; ++c)
        {
            cnt += A[r][c];
        }
    }
    cout << cnt;
}

void solve()
{
    initA();
    for(int i=0; i<M; ++i)
    {
        spellStart();
    }
    checkCloud();
    countAWater();
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();

    return 0;
}

후기

• 더 짧게 풀 수 없을까?
• 함수가 참 많고 코드가 참 길다.