[ BOJ - 21610번 ] 마법사 상어와 비바라기 (C++)

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

[ 풀이 방법 ]

 

비구름 생성 -> 이동 -> 바구니의 물의 양 증가 -> 비구름 제거 -> 물복사버그

위 과정이 반복된다.

 

1. 비구름을 생성하는 기능

  - 2차원 배열인 board를 이용해 바구니의 뮬의 양을 저장한다.

  - 2차원 배열인 rain을 이용해 비구름의 위치를 저장한다.

  - 2차원 배열인 pre를 이용해 비구름이 제거된 위치를 저장한다.

 

  - 첫 비구름은 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 생성된다.

      - rain 배열의 좌측 하단 4칸을 true로 초기화한다.

 

  - 그 이외의 비구름은 바구니에 담긴 물의 양이 2 이상인 칸의 위치에서 생성된다.

      - 이 때, 바구니의 물의 양이 2 줄어든다.

      - 이전 반복에서 해당 위치의 비구름이 제거되었다면 현재 반복에서는 해당 위치에서 비구름이 생성되지 않는다.

if(board[i][j] >= 2 && !pre[i][j]) {
	rain[i][j] = true;
	board[i][j] -= 2;
}

 

 

2. 비구름 이동 기능

  - 비구름을 d방향으로 s칸 이동시킨다.

  - 격자의 첫 행과 마지막 행, 첫 열과 마지막 열은 이어져 있다고 가정한다.

  - ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 순서로 방향을 저장하여 사용한다.

int dirX[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int dirY[8] = {-1, -1, 0, 1, 1, 1, 0, -1};

int nx = x + (dirX[d]*s)%N;
int ny = y + (dirY[d]*s)%N;
                
if(nx >= 0) nx %= N;
else nx = N + nx;
                
if(ny >= 0) ny %= N;
else ny = N + ny;

  - 비구름 이동 시, AUX 배열 사용하여 순서에 따라 이동에 영향이 가지 않게 한다.

 

3. 바구니의 물의 양 증가시키는 기능

4. 비구름 제거 기능

  - 비구름이 이동한 위치의 바구니의 물의 양을 1 증가시킨다.

  - 비구름을 제거하고 제거되기 전 위치를 표시한다.

for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
        if(rain[i][j]) {
            board[i][j]++;
            rain[i][j] = false;
            pre[i][j] = true;
        }
    }
}

 

5. 물복사버그 마법 수행 기능

  - board를 탐색하여 비구름이 제거된 위치라면 대각선 위치에 물이 담겨있는 칸의 개수를 센다.

  - 물이 있는 칸의 개수만큼 board의 칸의 물을 증가시킨다.

    - 이 때, 이동과 달리 board의 경계를 넘어갈 수 없다.

 

[ 회고 ]

  비구름의 생성이 반복의 시작이 아니라 비구름의 이동이 반복의 시작이라는 것을 생각하지 못해 예제 입력에서 틀린 결과가 나왔으나, 반복의 시작과 종료 위치를 수정하여 문제를 해결하고 정답을 맞출 수 있었다.

 

 문제 이해가 아쉬었으나 상대적으로 쉬운 문제이기도 했고 풀이 방법과 구현 계획, 구현과 검증이 잘 됐기 때문에 빠르게 문제를 해결하고 문제를 해결할 수 있었다.

 

[ 정답 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>

#define D first
#define S second

using namespace std;

int N, M;

typedef pair<int, int> Move;

vector<vector<int>> board;
vector<vector<bool>> rain;
vector<vector<bool>> pre;

vector<Move> moves;

int dirX[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int dirY[8] = {-1, -1, 0, 1, 1, 1, 0, -1};

int res;

void init() {
    for(int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }
    
    for(int i = 0; i < M; i++) {
        int d, s;
        cin >> d >> s;
        d--;
        moves.push_back(make_pair(d, s));
    }
}

void move(int idx) {
    vector<vector<bool>> aux(N, vector<bool>(N));
    int d = moves[idx].D;
    int s = moves[idx].S;
    
    for(int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            
            if(rain[i][j]) {
                int nx = i + (dirX[d]*s)%N;
                int ny = j + (dirY[d]*s)%N;
                
                if(nx >= 0) nx %= N;
                else nx = N + nx;
                
                if(ny >= 0) ny %= N;
                else ny = N + ny;
                
                aux[nx][ny] = true;
            }
            
        }
    }
    
    rain.swap(aux);
    vector<vector<bool>>().swap(aux);
}

void waterCopy() {
    
    vector<vector<int>> aux(board.begin(), board.end());

    for(int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            
            if(!pre[i][j]) continue;
                
            int cnt = 0;
            
            for(int d = 1; d < 8; d+=2) {
                int nx = i + dirX[d];
                int ny = j + dirY[d];
                
                if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                
                if(board[nx][ny]) cnt++;
            }
            
            aux[i][j] += cnt;
        }
    }
    
    board.swap(aux);
    vector<vector<int>>().swap(aux);
}

void solve() {
    
    int seq = 0;
    while(true) {
        
        // 비구름 생성
        if(seq == 0) {
            for(int i = N-2; i <= N-1; i++) {
                for(int j = 0; j < 2; j++) {
                    rain[i][j] = true;
                }
            }
        } else {
            for(int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(board[i][j] >= 2 && !pre[i][j]) {
                        rain[i][j] = true;
                        board[i][j] -= 2;
                    }
                    pre[i][j] = false;
                }
            }
        }
        if(seq >= M) return;
        
        // 비구름 이동
        move(seq);
        
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(rain[i][j]) {
                    board[i][j]++;
                    rain[i][j] = false;
                    pre[i][j] = true;
                }
            }
        }
        
        // 물복사
        waterCopy();
        seq++;
    }
}

void calc() {
    for(int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            res += board[i][j];
        }
    }
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M;
    
    board.resize(N, vector<int>(N));
    rain.resize(N, vector<bool>(N));
    pre.resize(N, vector<bool>(N));
    
    init();
    solve();
    calc();
    
    cout << res << '\n';
    
    return 0;
}