[BOJ] 21610 - 마법사 상어와 비바라기

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

21610번: 마법사 상어와 비바라기

난이도

단순구현 / 난이도 ⭐️⭐️ / 1.5시간 / 실수할 수 있는 부분 있음

문제 풀이

(문제 일부)

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에서 구름이 사라진 칸이 아니어야 한다.

단순 구현 문제이다.

1) 문제를 읽으면서 4번에서 배열4칸을 순차적으로 돌면서 바로바로 증가한 물을 반영할지, 따로 기억해뒀다가 한번에 증가시킬지 고민했으나, 2번 조건에서 구름이 있는 칸은 1증가 조건이 존재하기 때문에 for 문을 돌면서 바로바로 물을 증가 시켜도 상관없다고 판단했다. 

2) newx = newx - n 부분을 잘못 설계했다.

 

#include <iostream>
#include <vector>
#include <stdio.h>
#include <utility>
using namespace std;

int main()
{
    int dirx[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};
    int diry[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
    int copyx[4] = {-1, -1, 1, 1};
    int copyy[4] = {-1, 1, -1, 1};
    int n, m;
    int arr[52][52] = {0};

    scanf("%d %d", &n, &m);

    vector<pair<int, int> > cloud;
    cloud.push_back(make_pair(n, 1));
    cloud.push_back(make_pair(n, 2));
    cloud.push_back(make_pair(n - 1, 1));
    cloud.push_back(make_pair(n - 1, 2));

    int num;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            scanf("%d ", &arr[i][j]);
        }
    }

    int d, s;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d %d", &d, &s);

        while (s > n) // Check Point 2)
        {
            s = (s - n);
        }
        int x, y;
        int newx, newy;
        for (int i = 0; i < cloud.size(); i++)
        {
            x = cloud[i].first;
            y = cloud[i].second;
            newx = x + (dirx[d] * s); // Check Point 2)
            newy = y + (diry[d] * s); // Check Point 2)
            if (newx > n)
            {
                newx = newx - n;
            }
            else if (newx < 1)
            {
                newx = newx + n;
            }

            if (newy > n)
            {
                newy = newy - n;
            }
            else if (newy < 1)
            {
                newy = newy + n;
            }

            arr[newx][newy] += 1;
            cloud[i].first = newx;
            cloud[i].second = newy;
        }

        int cross_cnt;
        int check[52][52] = {0};
        for (int i = 0; i < cloud.size(); i++)
        {
            x = cloud[i].first;
            y = cloud[i].second;
            cross_cnt = 0;

            for (int j = 0; j < 4; j++)
            {
                newx = x + copyx[j];
                newy = y + copyy[j];
                if (newx > n | newx<1 | newy> n | newy < 1)
                    continue;

                if (arr[newx][newy] > 0)
                    cross_cnt += 1;
            }
            arr[x][y] += cross_cnt; // Check Point 1) 물을 바로 증가 시켜도 다음 for문과 상관없다.
            check[x][y] = 1;
        }

        cloud.clear();
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (arr[i][j] >= 2 && check[i][j] == 0)
                {
                    arr[i][j] -= 2;
                    cloud.push_back(make_pair(i, j));
                }
            }
        }
    } 

    int total_cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            total_cnt += arr[i][j];
        }
    }

    printf("%d\n", total_cnt);
}

 

주의 조건

n * n 배열을 기준으로 "d방향으로 s만큼 이동한다." (1 ≤ s ≤ 50)

 

예시) 5 * 5 배열을  기준으로 "d방향으로 12만큼 이동한다."

5 * 5 배열에서 구름이 어떤 방향이든 12만큼 이동하면 2만큼 이동한것과 똑같은 결과이다. 5만큼 이동할때마다 같은 자리로 돌아오기 때문이다. 따라서 아래 조건을 추가해주어야 비효율적인 이동을 하지 않는다.

while(s < n){
	s -= n;
}

 

처음에 위 조건을 추가해주지 않아서 s 가 클경우, 오답이 나왔다.

 

위 조건을 추가해주지 않을거면, 기준 배열에서 벗어났을 경우 위치를 보정해 주는 아래 코드를 수정해야한다.

s가 클 경우에는, 단순히 newx = newx -n 으로는 기준 배열 위치로 돌아오지 않는다.

하지만 굳이 아래 코드를 수정하지 않아도 위 조건을 추가하면 쉽게 해결가능하다.

newx = x + (dirx[d] * s);
newy = y + (diry[d] * s);
if (newx > n){
    newx = newx - n;
}else if (newx < 1){
    newx = newx + n;
}

if (newy > n){
    newy = newy - n;
}else if (newy < 1){
    newy = newy + n;
}