백준 21610번 마법사 상어와 비바라기 [C++]/삼성 SW역량 테스트 기출 문제

https://www.acmicpc.net/status?user_id=dfdfg1&problem_id=21610&from_mine=1

 

#문제 간단 정리

문제 그대로 잘 따라가기만 하면 되는 구현문제이다

다만 구현을 하면서 나름 주의해야 될 점들이 있으니 주의하자.

 

#문제 해결 방법

 

우선 구현해야될건

구름 이동함수 move

그리고 경계 처리를 위한 isBoundary 함수

물 복사 함수 makeWater

구름 생성 함수 makeCloud

 

그리고 순서에 따라서

구름 이동하기 -> 물 복사 -> 구름생성

 

을 구현한 함수를 차례대로 실행시켜주면 된다.

 

여기서 구름은 isCloud 2중 벡터로 추적하는데 주의해야 될점은

void move(int d, int s) {
    vector<vector<bool>> tempCloud(N + 1, vector<bool>(N + 1, false));

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (isCloud[i][j]) { 
                int ny = isBoundary(i + (s * dy[d - 1]));
                int nx = isBoundary(j + (s * dx[d - 1]));  

                tempCloud[ny][nx] = true; 
                mapVec[ny][nx] += 1;   
            }
        }
    }

    isCloud = tempCloud;  
}

 

여기서 처럼 temCloud 배열을 전부 false 로 선언한 후에

isCloud 를 이용하여 이동한 구름들을 기록하고

이 이동한 구름을

isCloud = tempCloud;

이런식으로 복사함으로써

 

기존의 isCloud 배열을 사용한후 이동한 기록을 복사함으로

구름의 이동을 구현 할 수 있다.

makeCloud 함수 구현도 같은 방식을 사용하고.

 

또 하나 주의해야 될 점은 구름 이동과 물 복사시에

경계처리를 주의하도록하자

N 다음에 1 이 오도록 경계를 확인하는

isBoundary 함수도 구현하는 것도 잊지 않는다면 무난하게 구현 가능하

 

#전체 코드

#include <iostream>
#include <stack>
#include <cctype> 
#include <vector>
#include <queue>

using namespace std;

int N, M;
//구름이동
int dx[8] = {-1,-1,0,1,1,1,0,-1}; 
int dy[8] = {0,-1,-1,-1,0,1,1,1};

//대각선 확인
int ddx[4] = {-1,1,-1,1};
int ddy[4] = {-1,-1,1,1};

vector<vector<int>> mapVec;
vector<vector<bool>> isCloud;

//원형으로 이어주기 위한 확인함수
int isBoundary(int x) {
    if (x > N) {
        x = x%N;
    }
    
    if (x < 1) {
        x = N + (x % N);
    }

    return x;
}
void move(int d, int s) {
    vector<vector<bool>> tempCloud(N + 1, vector<bool>(N + 1, false));

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (isCloud[i][j]) { 
                int ny = isBoundary(i + (s * dy[d - 1]));
                int nx = isBoundary(j + (s * dx[d - 1]));  

                tempCloud[ny][nx] = true; 
                mapVec[ny][nx] += 1;   
            }
        }
    }

    isCloud = tempCloud;  
}

void waterCopy() {

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {

            if (isCloud[i][j]) {
                int count = 0;
                for (int dir = 0; dir < 4; dir++) {
                    int nx = j + ddx[dir], ny = i + ddy[dir];
                    if (nx >= 1 && nx <= N && ny >= 1 && ny <= N && mapVec[ny][nx] > 0) {
                        count++;
                    }
                }
                mapVec[i][j] += count;
            }
        }
    }


}

void makeCloud() {
    vector<vector<bool>> newCloud(N + 1, vector<bool>(N + 1, false));
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (!isCloud[i][j] && mapVec[i][j] >= 2) {
                newCloud[i][j] = true;
                mapVec[i][j] -= 2;
            }
        }
    }
    isCloud = newCloud;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N >> M;


    mapVec.resize(N+1, vector<int>(N + 1, 0));
    isCloud.resize(N + 1, vector<bool>(N + 1, false));

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> mapVec[i][j];
        }
    }

    isCloud[N][1] = true;
    isCloud[N][2] = true;
    isCloud[N-1][1] = true;
    isCloud[N-1][2] = true;
   
    for (int i = 0; i < M; i++) {
        int d, s;
        cin >> d >> s;

        move(d, s);
        waterCopy();
        makeCloud();
    }

    //물 합산
    int result = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {  
            result += mapVec[i][j];
        }
    }

    cout << result << '\n';

    return 0;
}