백준 23290번 : 마법사 상어와 복제 - 시뮬레이션 C++

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

23290번: 마법사 상어와 복제

물고기를 한마리 한마리 처리하는 게 아니라

같은 좌표에서 같은 방향을 가리키는 물고기가 몇마리 있는 지 세어주는 식으로 구현하면

메모리를 상당히 아낄 수 있다.

 

처음에 문제를 읽을 때는 물고기 한마리 한마리 벡터에 넣어주면서 풀었는데

어차피 중요한건 물고기의 수이므로 같은 좌표 같은 방향 물고기를 한번에 이동시켜주면

메모리와 함께 시간도 절약할 수 있다.

 

그리고 상어의 이동은 3칸이동하므로 간단히 반복문으로 구현하고

이동 내에서 중복된 칸이 있는지 체크하기 위해 set을 이용하여 여러번 방문한 칸이어도

물고기들을 한번만 없애주도록 만들었다.

 

#include <bits/stdc++.h>

using namespace std;

int skx, sky, S, smell[5][5];
int fishes[5][5][9], fishCopy[5][5][9];

void Input() {
    int M;
    cin >> M >> S;
    for (int i = 1; i <= M; i++) {
        int fx, fy, d;
        cin >> fx >> fy >> d;
        fishes[fx][fy][d]++;
    }
    cin >> skx >> sky;
}

void copyMagic() {
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            for (int k = 1; k <= 8; k++) {
                fishCopy[i][j][k] = fishes[i][j][k];
            }
        }
    }
}

void fishesMove() {
    int dx[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};
    int dy[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1};

    int tmp[5][5][9];
    memset(tmp, 0, sizeof(tmp));
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            for (int k = 1; k <= 8; k++) {
                int dir = k;
                bool flag = false;
                for (int t = 1; t <= 8; t++) {
                    int nx = i + dx[dir];
                    int ny = j + dy[dir];
                    if (nx <= 0 || nx > 4 || ny <= 0 || ny > 4 || smell[nx][ny] || (nx == skx && ny == sky)) {
                        //반시계회전
                        dir = dir - 1;
                        if (dir == 0) dir = 8;
                    } else {
                        flag = true;
                        tmp[nx][ny][dir] += fishes[i][j][k];
                        break;
                    }
                }
                //이동할 수 없는 경우
                if (!flag) {
                    tmp[i][j][k] += fishes[i][j][k];
                }
            }
        }
    }
    swap(tmp, fishes);
}

void sharkMove() {
    int dx[5] = {0, -1, 0, 1, 0};
    int dy[5] = {0, 0, -1, 0, 1};

    int maxSum = -1;
    int nskx = -1, nsky = -1;
    vector<pair<int, int> > toSmell;
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            for (int k = 1; k <= 4; k++) {
                int firstX = skx + dx[i], firstY = sky + dy[i];
                int secX = firstX + dx[j], secY = firstY + dy[j];
                int thirdX = secX + dx[k], thirdY = secY + dy[k];

                if (firstX <= 0 || firstX > 4 || firstY <= 0 || firstY > 4) continue;
                if (secX <= 0 || secX > 4 || secY <= 0 || secY > 4) continue;
                if (thirdX <= 0 || thirdX > 4 || thirdY <= 0 || thirdY > 4) continue;
                int sum = 0;
                set<pair<int, int> > Set;
                Set.insert({firstX, firstY});
                Set.insert({secX, secY});
                Set.insert({thirdX, thirdY});
                for (auto a: Set) {
                    for(int b=1; b<=8; b++){
                        sum += fishes[a.first][a.second][b];
                    }
                }
                if (sum > maxSum) {
                    maxSum = sum;
                    toSmell.clear();
                    nskx = thirdX;
                    nsky = thirdY;
                    for (auto a: Set) {
                        toSmell.push_back({a.first, a.second});
                    }
                }
            }
        }
    }
    for (auto a: toSmell) {
        int sum = 0;
        for(int b=1; b<=8; b++){
            sum += fishes[a.first][a.second][b];
        }
        if (sum) {
            smell[a.first][a.second] = 3;
            memset(fishes[a.first][a.second], 0 ,sizeof(fishes[a.first][a.second]));
        }
    }
    skx = nskx;
    sky = nsky;
}

void smellErase() {
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            if (smell[i][j]) {
                smell[i][j]--;
            }
        }
    }
}

void appendCopy() {
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            for(int k=1; k<=8 ;k++){
                fishes[i][j][k] += fishCopy[i][j][k];
            }
        }
    }
}

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

    Input();
    for (int i = 0; i < S; i++) {
        copyMagic();
        fishesMove();
        sharkMove();
        smellErase();
        appendCopy();
    }

    int ans = 0;
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            for(int k=1; k<=8 ;k++){
                ans += fishes[i][j][k];
            }
        }
    }

    cout << ans << '\n';

    return 0;
}