골랜디 #11 21610번

Published at: 2025-03-30

Last modified at: 2025-03-30

안녕하세요 한라나입니다.
오늘도 방송에서 엘든링을 했어요. 아마 내일도 할 거에요.
오늘은 패링이란걸 처음 배웠습니다. 전 지금까지 가드카운터가 패링인줄 알았어요?
정말 나쁜 게임임을 느낍니다.

각설하고 오늘의 문제는 아래와 같습니다.

21610

빡구현 문제… 일단 n의 범위가 작아서 시키는 것 그대로 해도 터질 것 같지는 않아 보입니다.

일단은 8가지 방향을 나타내는 배열을 하나 만들어 줬습니다.

int direction[8][2] = { {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1} };

그리고 메인 배열인 A에 대해서는, 오늘은 1부터 시작하는 인덱스를 사용합니다.
왜냐하면 위치가 n이나 1을 넘어가면 범위 내로 다시 끌고와야 하고, 대각선 바구니에 있는 물들도 고려를 해야 하기 때문입니다.
끝행, 끝열에 있는 녀석들은 어차피 유효하지 않은 대각선 방향에는 0이 들어 있으니까, 예외를 두지 않고 한번에 보기 편합니다.

구름에 대해서는 큐를 사용했어요. 구름이 생성되면 큐에 넣고, 그 구름들을 다 빼서 비 오고 물 복사하고 등등을 하기가 편합니다.
그리고 추가로 비 내린 칸을 저장하는 큐도 하나 만들었고, 비 내린 칸을 저장하는 배열도 하나 만들었습니다.
둘 중에 하나만 해도 되지만, 그냥 이렇게 하는게 이뻐 보였어요.

과정은 다음과 같습니다.

d, s를 입력받음.
구름이 들어있는 큐가 빌 때까지 하나씩 빼 와서, 방향 d로 s만큼 이동시킨 후,
인덱스를 1~n 범위로 조정한 다음 그 칸에 물을 뿌리고 비 내린 칸을 저장하는 큐, 배열에 기록함.
비 내린 칸이 저장되어있는 큐가 빌 때까지 해당 칸들의 대각선을 검사하여 물이 들어있는 칸 수 만큼 물을 복사함.
물이 2 이상 들었고, 비가 내리지 않은 칸을 구름이 들어있는 큐에 집어넣고 물을 2개 뺌.

시작할때는 (N, 1), (N, 2), (N-1, 1), (N-1, 2) 칸이 구름이 들어있는 큐에 들어가 있으면 됩니다.

bool check[55][55];
for(i=1;i<=n;i++) {
    for(j=1;j<=n;j++) {
        check[i][j] = false;
    }
}
int d, s;
scanf("%d %d", &d, &s);
while(!clouds.empty()) {
    auto k = clouds.front();
    clouds.pop();
    k.first += direction[d-1][0] * s;
    k.second += direction[d-1][1] * s;
    k.first = ((k.first+50*n-1) % n) + 1;
    k.second = ((k.second+50*n-1) % n) + 1;
    A[k.first][k.second]++;
    waterCopy.push({k.first, k.second});
    check[k.first][k.second] = true;
}
while(!waterCopy.empty()) {
    auto k = waterCopy.front();
    waterCopy.pop();
    int basket = 0;
    for(j=1;j<5;j++) {
        if(A[k.first+direction[j*2-1][0]][k.second+direction[j*2-1][1]]>0) basket++;
    }
    A[k.first][k.second] += basket;
}
for(i=1;i<=n;i++) {
    for(j=1;j<=n;j++) {
        if((A[i][j]>1)&&(!check[i][j])) {
            clouds.push({i, j});
            A[i][j] -= 2;
        }
    }
}

저는 빡구현이 밉습니다.

감사합니다.

streak

전체 코드

#include <stdio.h>
#include <queue>

using namespace std;

queue< pair< int, int > > clouds;
queue< pair< int, int > > waterCopy;
int direction[8][2] = { {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1} };

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int A[55][55] = {0, };
    int i, j, l;
    for(i=1;i<=n;i++) {
        for(j=1;j<=n;j++) {
            scanf("%d", &A[i][j]);
        }
    }
    clouds.push({n, 1});
    clouds.push({n, 2});
    clouds.push({n-1, 1});
    clouds.push({n-1, 2});
    for(l=0;l<m;l++) {
        bool check[55][55];
        for(i=1;i<=n;i++) {
            for(j=1;j<=n;j++) {
                check[i][j] = false;
            }
        }
        int d, s;
        scanf("%d %d", &d, &s);
        while(!clouds.empty()) {
            auto k = clouds.front();
            clouds.pop();
            k.first += direction[d-1][0] * s;
            k.second += direction[d-1][1] * s;
            k.first = ((k.first+50*n-1) % n) + 1;
            k.second = ((k.second+50*n-1) % n) + 1;
            A[k.first][k.second]++;
            waterCopy.push({k.first, k.second});
            check[k.first][k.second] = true;
        }
        while(!waterCopy.empty()) {
            auto k = waterCopy.front();
            waterCopy.pop();
            int basket = 0;
            for(j=1;j<5;j++) {
                if(A[k.first+direction[j*2-1][0]][k.second+direction[j*2-1][1]]>0) basket++;
            }
            A[k.first][k.second] += basket;
        }
        for(i=1;i<=n;i++) {
            for(j=1;j<=n;j++) {
                if((A[i][j]>1)&&(!check[i][j])) {
                    clouds.push({i, j});
                    A[i][j] -= 2;
                }
            }
        }
    }
    int ans = 0;
    for(i=1;i<=n;i++) {
        for(j=1;j<=n;j++) {
            ans += A[i][j];
        }
    }
    printf("%d", ans);
    return 0;
}