백준 19237번 : 어른 상어 - 구현, 시뮬레이션 C++

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

19237번: 어른 상어

1.문제설명

구현해야할 부분 단위가 많은 시뮬레이션 문제이다.

 

각 부분에 대하여 기능을 잘 분리하고

올바른 순서로 기능을 수행해야 문제를 해결 할 수 있다.

 

주의해야할 점은

모든 상어가 동시에 움직이고 동시에 냄새를 뿌린다는 점이다.

 

즉 상어가 움직이면서 냄새를 뿌리도록 구현하면

잘못된 구현이다.

 

 

 

크게 구현해야할 것은

1. 턴 마다 상어 움직이기

2. 냄새 뿌리기

3. 1번 상어만 남아있는지 확인하기

 

1번을 구현하기 위해서 부분 문제로

각 상어마다 방향정보를 바탕으로

이동해야할 위치와 방향을 구해야한다.

 

이 때 모든 상어는 동시에 움직인다는 조건을 지니므로

상어의 위치를 각 상어마다 옮기고 바로 적용해주는 것이 아니라

현재 위치와 다음 턴의 위치를 구분 짓기 위해서

다른 배열을 하나 두어서 체크를 해주는 것도 중요한 포인트다.

 

 

---

 

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int N, M, K;
int sharkState[500][3];
int dirPriority[500][5][5];
//20X20 (smell, shark)
int smell[30][30][2];

int dx[5] = {0, -1, 1, 0, 0};
int dy[5] = {0, 0, 0, -1, 1};


void Input();


void sharkNextState(int sharkNum, int &x, int &y, int &d) {
    int curX = x;
    int curY = y;
    int curD = d;

    //먼저 현재 방향으로 이동 가능한지 체크
    int nx = -1;
    int ny = -1;
    int nd = -1;

    for (int i = 1; i <= 4; i++) {
        nd = dirPriority[sharkNum][curD][i];
        nx = curX + dx[nd];
        ny = curY + dy[nd];

        if (nx <= 0 || nx > N || ny <= 0 || ny > N) continue;
        if (smell[nx][ny][0] > 0) continue;
        x = nx;
        y = ny;
        d = nd;
        return ;
    }

    //네 방향모두 냄새로 가득 차있으니 자신의 냄새있는 칸 찾기
    for (int i = 1; i <= 4; i++) {
        nd = dirPriority[sharkNum][curD][i];
        nx = curX + dx[nd];
        ny = curY + dy[nd];

        if (nx <= 0 || nx > N || ny <= 0 || ny > N) continue;
        if (smell[nx][ny][1] != sharkNum) continue;
        x = nx;
        y = ny;
        d = nd;
        return;
    }
}


void allSharkCheck() {
    bool nextMap[30][30] = {0};
    for (int i = 1; i <= M; i++) {
        int curX = sharkState[i][0];
        int curY = sharkState[i][1];
        int curD = sharkState[i][2];

        //죽은 상어 제외
        if (curX < 0) continue;
        sharkNextState(i, curX, curY, curD);

        //번호 작은 상어 이미 존재
        if (nextMap[curX][curY]) {
            sharkState[i][0] = -1;
            continue;
        }

        sharkState[i][0] = curX;
        sharkState[i][1] = curY;
        sharkState[i][2] = curD;
        nextMap[curX][curY] = 1;
    }
}


bool gameEndCheck() {
    //1번 상어 살아 있고
    if (sharkState[1][0] < 0) return false;
    //다른 상어 모두 죽었을 때
    for (int i = 2; i <= M; i++) {
        if (sharkState[i][0] > 0) {
            return false;
        }
    }
    return true;
}

void spreadSmell(){
    for (int i = 1; i <= M; i++) {
        int curX = sharkState[i][0];
        int curY = sharkState[i][1];
        if (curX < 0) continue;
        smell[curX][curY][0] = K;
        smell[curX][curY][1] = i;
    }
}


void decrementSmell(){
    for(int i=1; i<=N;i++){
        for(int j=1; j<=N; j++){
            if(smell[i][j][0]>0){
                smell[i][j][0]--;
            }
        }
    }
}

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

    Input();
    for (int i = 1; i <= 1000; i++) {
        spreadSmell();
        allSharkCheck();
        if (gameEndCheck()) {
            cout << i << '\n';
            return 0;
        }
        decrementSmell();
    }
    cout << -1 << '\n';
}


void Input() {
    cin >> N >> M >> K;
    //x, y
    for (int x = 1; x <= N; x++) {
        for (int y = 1; y <= N; y++) {
            int sk;
            cin >> sk;

            if (sk > 0) {
                sharkState[sk][0] = x;
                sharkState[sk][1] = y;
            }
        }
    }
    //dir
    for (int i = 1; i <= M; i++) {
        cin >> sharkState[i][2];
    }

    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= 4; j++) {
            for (int k = 1; k <= 4; k++) {
                cin >> dirPriority[i][j][k];
            }
        }
    }
}