[C++] 백준 21610 마법사 상어와 비바라기

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

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

1. 서론

 

삼성 기출 중에서 시뮬레이션 문제 풀려고 풀어봤던 문제. 생각보다 구조 자체는 간단한데 시뮬레이션답게 제약조건 고치는 것만 100시간 걸린 듯 ㅎㅎ 결국엔 인터넷에서 약간 힌트를 찾아서 풀었다.

 

2. 문제풀이

 

배열이 주어진다. 주어진 배열 칸에는 물의 양이 적혀있다. 그리고 그 위로 구름이 지나간다고 가정한다. 구름은 상하좌우, 대각선까지 8가지 방향으로 움직일 수 있다.

 

1) 구름이 지정된 방향대로 이동함

2) 구름이 위치한 곳에 비가 1씩 내리고 구름이 사라짐

3) 구름 위치를 기준으로 대각선 4방에 물이 있으면 있는 칸의 양만큼 현재칸의 물의 양이 증가함

4) 위의 루틴이 끝난 후 물의 양이 2 이상인 곳에 구름이 생김 구름이 생기면 물의 양이 2 감소함

 

이 과정을 n번 하고 났을때 전체 배열에 물의 양이 얼마나 남는지 구하는 문제이다. 

그래서 이 과정을 함수로 쪼개서 구현했다.

 

1번은 move()

2,3번은 rain()

4번은 cloud()

 

근데 move 함수에서 구름이 범위 앞뒤로 넘나드는 게 제대로 안 되는 것 같아서 인터넷을 찾아봤고 make_range함수를 가져다가 배열의 범위를 넘었을 경우를 처리해줬다.

 

 

3. 코드 설명

 

#include <vector>
#include <iostream>

using namespace std;

int a[51][51], board[51][51], n;
int dx[] = {0, 0, -1, -1, -1, 0, 1, 1 , 1};
int dy[] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
 
int make_range(int x)
{
    if (x < 0) return n - 1;
    if (x >= n) return 0;
    return x;
}

void move(int d, int s)
{
    int t[n][n], i, j , x, y;

    for (i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            t[i][j] = 0;

    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (board[i][j] == 1)
            {
                x = i, y = j;
                for (int k = 0; k < s; k++)
                {
                    x += dx[d];
                    y += dy[d];
                    x = make_range(x);
                    y = make_range(y);
                }
                 t[x][y] = 1;
            }
        }
    }

    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            board[i][j] = t[i][j];
    return;
}

void rain()
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (board[i][j] == 1)
                a[i][j]++;  

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (board[i][j] == 1)
            {
                if (a[i - 1][j - 1] > 0 && i - 1 >= 0 && j - 1 >= 0)
                    a[i][j]++;
                if (a[i - 1][j + 1] > 0 && i - 1 >= 0 && j + 1 < n)
                    a[i][j]++;  
                if (a[i + 1][j + 1] > 0 && i + 1 < n && j + 1 < n)
                    a[i][j]++;
                if (a[i + 1][j - 1] > 0 && i + 1 < n && j - 1 >= 0)
                    a[i][j]++; 
            }
        }
    }
    return; 
}

void cloud()
{
    int t[n][n];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            t[i][j] = board[i][j];
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (a[i][j] >= 2)
                board[i][j] = 1;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (t[i][j] == 1)
                board[i][j] = 0;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (board[i][j] == 1)
            {
                a[i][j] -= 2;
                if (a[i][j] < 0)
                    a[i][j] = 0;
            }
        }
    }
    return;
}

int main()
{
    int m, i, j, x, y, sum = 0;

    cin >> n >> m;

    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            cin >> a[i][j];

    vector<pair<int, int> > v;
    for (i = 0; i < m; i++)
    {
        cin >> x >> y;
        v.push_back(make_pair(x, y));
    }

    for (i = 0; i <= n; i++)
        for (j = 0; j <= n; j++)
            board[i][j] = 0;
    
    board[n - 1][0] = 1, board[n - 1][1] = 1, board[n - 2][0] = 1, board[n - 2][1] = 1;

    for (i = 0; i < m; i++)
    {
        move(v[i].first, v[i].second);
        rain();
        cloud();
    }

    for (i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            sum += a[i][j];
    
    cout << sum << endl;
}

 

input 값을 입력받는다. 배열 a는 비의 양을 저장하고 board는 구름의 위치를 저장한다.

move함수에서 board[i][j] 의 값이 1일 때, 즉 구름일 때 좌표를 이동시켜준다. 이때 make_range로 n보다 클 때나 0보다 작을 때의 경곗값을 처리해준다. 배열 t는 tmp역할을 해주는 배열로 실시간으로 board배열의 값이 바뀌면 반복문을 돌다가 계산이 바뀔 수도 있기 때문에 사용해줬다. rain, cloud 배열에서도 마찬가지로 위에서 설명한 역할을 하는 코드를 구현하고 t배열을 사용했다.

(t 사용 안했다가 처음에 값이 이상하게 나와서 헤맸음. + rain함수에서 배열 범위 처리...)