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

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

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

알고리즘도 중요하지만 복잡한 구현 과정에서 실수하지 않는 것도 중요한 것 같다.

그래서 틈틈이 2차원 배열에서 원소들을 이동하는 문제를 풀어보았다.

 

가장 먼저 순서대로 주어진 일을 수행해야 한다. 이를 제대로 파악하기 위해 나는 함수별로 주어진 일을 나누었다.

- move → 구름의 이동 및 구름의 물의 양 증가

- copy_bug → 물복사 버그

- make_cloud → 구름 생성

 

여기서 제일 어려운 점은 구름을 이동하는 것이었다.

끝 행과 끝 열이 모두 연결되어있고, $s_i$가 격자의 크기보다 더 큰 경우가 있기에 구름을 이동하는 것이 어려웠다.

이를 해결 하기 위해 몇 가지 장치들을 두었다.

 

📌 $s_i$가 격자의 크기보다 큰 경우

modulo 연산을 사용해 n보다 작지만 $s_i$와 결과가 동일하도록 만든다.

 

📌 이동 시 격자의 경계를 벗어나는 경우

modulo 연산을 사용해 격자 내부의 값을 기록한다.

그런데 음수의 경우도 고려해야 하므로 연산 전에 n을 더해야 한다.

양수의 경우에는 n을 더하는 것이 결과에 영향을 주지 않는다.

 

void move(vector<vector<int>> &map, int d, int s) {
    set<pair<int,int>> moved;
    if(s >= n) {
        s = s % n;
    }
    for(auto cloud: clouds) {
        int nr = (cloud.first + n + (dr[d] * s)) % n;
        int nc = (cloud.second + n + (dc[d] * s)) % n;
        
        moved.insert({nr, nc});
        map[nr][nc] += 1;
    }
    clouds = moved;
}

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int n, m;
set<pair<int, int>> clouds;

int dr[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int dc[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
void move(vector<vector<int>> &map, int d, int s) {
    set<pair<int,int>> moved;
    if(s >= n) {
        s = s % n;
    }
    for(auto cloud: clouds) {
        int nr = (cloud.first + n + (dr[d] * s)) % n;
        int nc = (cloud.second + n + (dc[d] * s)) % n;
        
        moved.insert({nr, nc});
        map[nr][nc] += 1;
    }
    clouds = moved;
}

bool inside(int r, int c) {
    return r >= 0 && r < n && c >= 0 && c < n;
}

void make_cloud(vector<vector<int>> &map){
    set<pair<int,int>> moved;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            if(map[i][j] >= 2 && clouds.find({i, j}) == clouds.end()) {
                moved.insert({i, j});
                map[i][j] -= 2;
            }
        }
    }
    
    clouds = moved;
}


void copy_bug(vector<vector<int>> &map) {
    for(auto cloud: clouds) {
        int r = cloud.first;
        int c = cloud.second;
        int cnt = 0;
        
        for(int i = 1;i < 8;i += 2) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            
            if(inside(nr, nc) && map[nr][nc] > 0) {
                cnt++;
            }
        }
        map[r][c] += cnt;
    }
}
int main() {

    cin >> n >> m;
    vector<vector<int>> map(n, vector<int> (n));
    for(int i = 0;i < n;i++) {
        for(int j = 0l;j < n;j++) {
            cin >> map[i][j];
        }
    }
    
    clouds.insert({n - 1, 0});
    clouds.insert({n - 1, 1});
    clouds.insert({n - 2, 0});
    clouds.insert({n - 2, 1});
    
    
    for(int i = 0;i < m;i++) {
        int d, s;
        cin >> d >> s;
        move(map, d - 1, s);
        
        copy_bug(map);
    
        make_cloud(map);
    }
    
    long long sum = 0;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            sum += map[i][j];
        }
    }
    
    cout << sum << '\n';
}