백준 21610 마법사 상어와 비바라기 (C++)

안유태·2023년 9월 27일
0

알고리즘

목록 보기
151/239

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

문제 로직을 직접 구현을 하는 문제이다. 푸는 법은 간단하다. 그냥 문제 설명 순서대로 구현하면 된다. 나는 설명 순서대로 step을 나누어 구분하였다. 문제 그대로 구현한 코드이므로 문제 지문과 비교하면서 읽어보면 바로바로 이해가 될 것이다. 어렵지 않게 풀 수 있었던 문제였다.



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

using namespace std;

int N, M;
int A[50][50];
vector<pair<int, int>> ds;
vector<pair<int, int>> cloud;
vector<pair<int, int>> tmp;
int dy[8] = { 0,-1,-1,-1,0,1,1,1 };
int dx[8] = { -1,-1,0,1,1,1,0,-1 };

void step1(int n) {
    int d = ds[n].first - 1;
    int s = ds[n].second;

    for (int i = 0; i < cloud.size(); i++) {
        int ny = cloud[i].first + dy[d] * (s % N);
        int nx = cloud[i].second + dx[d] * (s % N);

        if (ny < 0) ny += N;
        if (nx < 0) nx += N;
        if (ny >= N) ny -= N;
        if (nx >= N) nx -= N;

        cloud[i] = { ny,nx };
    }
}

void step2() {
    for (int i = 0; i < cloud.size(); i++) {
        int y = cloud[i].first;
        int x = cloud[i].second;

        A[y][x]++;

        tmp.push_back({ y,x });
    }
}

void step3() {
    cloud.clear();
}

void step4() {
    int dd[4] = { 1,3,5,7 };

    for (int i = 0; i < tmp.size(); i++) {
        int y = tmp[i].first;
        int x = tmp[i].second;

        for (int j = 0; j < 4; j++) {
            int ny = y + dy[dd[j]];
            int nx = x + dx[dd[j]];

            if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;

            if (A[ny][nx] > 0) A[y][x]++;
        }
    }
}

void step5() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (A[i][j] < 2) continue;

            bool tf = false;
            for (int k = 0; k < tmp.size(); k++) {
                if (i == tmp[k].first && j == tmp[k].second) tf = true;
            }
            if (tf) continue;

            cloud.push_back({ i,j });
            A[i][j] -= 2;
        }
    }

    tmp.clear();
}

void solution() {
    cloud.push_back({ N - 1,0 });
    cloud.push_back({ N - 1,1 });
    cloud.push_back({ N - 2,0 });
    cloud.push_back({ N - 2,1 });

    for (int i = 0; i < M; i++) {
        step1(i);
        step2();
        step3();
        step4();
        step5();
    }

    int result = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            result += A[i][j];
        }
    }

    cout << result;
}

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

    cin >> N >> M;

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

    int d, s;
    for (int i = 0; i < M; i++) {
        cin >> d >> s;
        ds.push_back({ d,s });
    }

    solution();

    return 0;
}
profile
공부하는 개발자

0개의 댓글