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

백준 특유의 병맛스러운 제목과 내용이 처음에는 거부감이 들었는데 읽으면 읽을수록 중독 되는거보면 난 백준이 좋은거같다. 이 문제는 마법사 상어 시리즈 중 하나인데 앞으로 블로그에 이런 비슷한 유형의 문제를 많이 올릴 생각이다.

이 문제는 여러가지 조건으로 이루어져 있는데 가장 핵심은 구름을 자유롭게 이동시키고 해당 요구사항에 맞게 Matrix 안에 있는 숫자를 변경시켜야지 풀 수 있었던 문제같다.

만약 중간에라도 어떤 부분에서 실수를 하게 된다면 처음부터 다시 쭉 봐야하기때문에 상당히 어지럽고 구현하는데 있어서집중을 많이 해야한다.

내가 최근들어 다른 알고리즘, backtracking, dp, two pointer 등등을 안푸는 이유 중 하나는 구현이 얼마나 중요한 스킬인지 느꼈기 때문이다. 특별한 알고리즘은 안들어가도 해당 설명에 맞춰서 구현을 하고 시뮬레이션에 맞는 코드를 짜는게 되게 핵심이라 생각해서 Matrix, DFS/BFS, Simulation 이 섞인 문제들을 위주로 풀고 있는 요즘이다.

index 같은 경우 헷갈릴수 있지만, M만큼만 확인 하면 되는것이기에 그 안에서 이동, 계산을 동시에 전부 해야한다. 시나리오에는 모든 좌표의 끝 부분이 연결 되어 있기때문에 저렇게 조건문을 적어주었다.

계산 부분 1 이 내가 실수를 했는데..구름이 이동한 후에 visited 를 표시해줘야 정답이 됐었다.

항상 memset 방법은 잊지말자

코드를 쓰는건 오래 안걸린거같은데 실수를 고치는게 훨씬 오래 걸렸었다...

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int N, M; 
int matrix[51][101]; 
bool visited[51][101]; 
vector<pair<int,int>> dir = {{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1}}; 
vector<pair<int,int>> command; 

void Input(){
    cin >> N >> M; 
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> matrix[i][j]; 
        }
    }
    for(int i = 0; i < M; i++){
        int d, s; cin >> d >> s;
        command.push_back({d,s}); 
    }
}

void Solution(){
    int answer = 0; 
    vector<pair<int,int>> cloud = {{N-1,0}, {N-1,1}, {N-2,0}, {N-2,1}}; //구름의 시작점 
    for(int index = 0; index < M; index++){
        //구름의 이동
        for(pair<int,int>& cloud_point : cloud){
            int arrow = command[index].first-1, num = command[index].second; 
            for(int i  = 0; i < num; i++){
                cloud_point.first += dir[arrow].first;
                cloud_point.second += dir[arrow].second;

                if(cloud_point.first < 0) cloud_point.first = N-1;
                if(cloud_point.second < 0) cloud_point.second = N-1; 

                if(cloud_point.first >= N) cloud_point.first = 0; 
                if(cloud_point.second >= N) cloud_point.second = 0; 
            }
        }

        // //계산 부분 1 : 구름에 있는 칸에 비가 1씩 내린다 
        for(pair<int,int>& cloud_point : cloud){
            int x = cloud_point.first, y = cloud_point.second;
            visited[x][y] = true; 
            matrix[x][y] += 1; 
        }

        // //계산 부분 2 : 물복사 버그(?) 각 좌표마다 대각선 방향으로 
        // //Matrix범위 안에있고 0이상이면은 그 숫자에 따라서 구름안에 있는 빗물의 양을 증가시킨다 
        for(pair<int,int>& cloud_point : cloud){
            int x = cloud_point.first, y = cloud_point.second, cnt = 0; 
            for(int i = 1; i < dir.size(); i+=2){
                int nX = x + dir[i].first;
                int nY = y + dir[i].second; 

                if(nX >= 0 && nX < N && nY >= 0 && nY < N && matrix[nX][nY] > 0){
                    cnt++; 
                }
            }
            matrix[x][y] += cnt; 
        }

        // //구름 칸 제외 나머지에서 칸이 2 이상이면은 그 칸에 구름이 생기고, 물의 양이 2만큼 줄어든다 
        // //visited 가 여기서 필요하다 -> 구름이 생성되면은 visited 에 표시해주자 
        cloud.clear(); //새 구름을 넣어야하기 때문에 비워둔다 
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(matrix[i][j] >= 2 && !visited[i][j]){
                    matrix[i][j] -= 2; 
                    cloud.push_back({i,j}); 
                }
            }
        }
        memset(visited,false,sizeof(visited)); //기존에 구름을 전부 제거해준다 
    }




    //전부 다 이동이 끝나고 구름이 완성되면 그 자리가 구름이 있었던 흔적인데 잘못 이해함;; 
    //그냥 구름이 생성되는 시작점을 흔적으로 남겼기때문에 이동 후에 좌표를 흔적으로 못남겼다


    //printing 
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            answer += matrix[i][j]; 
        }
    }

    cout << answer; 

}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}

배운점:
1. Simulation 능력
2. 문제를 정말로...잘 읽자