백준 19237번 - 어른 상어 (C++)

문제

 

해결 방법

문제에 써있는 그대로 구현하는 문제이다. 때문에 좌표, 자신의 규칙을 담는 4x4 2차원 배열[방향][우선순위], 순서, 방향을 담는 shark 클래스를 만들어서 진행하였다.

아쉬웠던 점

없다.

코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <string.h>
#include <tuple>
using namespace std;
 
int UDLRy[4] = {0,0,-1,1};
int UDLRx[4] = {-1,1,0,0};
 
class Shark
{
public:
    int X, Y;
    int Dir;
    int Rule[4][4];
    int Num;
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int N, M, K;
    pair<int, int> Map[20][20]; //상어번호, 냄새 지속시간
    cin >> N >> M >> K;
    vector<Shark> SharkVec(M);
 
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
        {
            int a;
            cin >> a;
            if (a != 0)
            {
                Map[i][j].first = a;
                Map[i][j].second = K;
                SharkVec[a - 1].X = i;
                SharkVec[a - 1].Y = j;
                SharkVec[a - 1].Num = a;
            }
            else
            {
                Map[i][j].first = 0;
                Map[i][j].second = 0;
            }
        }
 
    for (int i = 0; i < M; ++i)
        cin >> SharkVec[i].Dir;
 
    for (int i = 0; i < M; ++i)
        for(int j = 0 ; j < 4; ++j)
            for (int k = 0; k < 4; ++k)
                cin >> SharkVec[i].Rule[j][k];
    
    int Time = 0;
    while (SharkVec.size() != 1)
    {
        Time++;
        if (Time == 1001)
        {
            cout << "-1";
            return 0;
        }
 
        //상어 이동
        for (auto &i : SharkVec)
        {
            bool Check = true;
            for (int j = 0; j < 4; ++j)
            {
                int Fx = i.X + UDLRx[i.Rule[i.Dir - 1][j] - 1];
                int Fy = i.Y + UDLRy[i.Rule[i.Dir - 1][j] - 1];
                if (Fx < 0 || Fx >= N || Fy < 0 || Fy >= N)
                    continue;
 
                if (Map[Fx][Fy].second == 0)
                {
                    i.X = Fx;
                    i.Y = Fy;
                    Check = false;
                    i.Dir = i.Rule[i.Dir - 1][j];
                    break;
                }
            }
            if (Check)
            {
                for (int j = 0; j < 4; ++j)
                {
                    int Fx = i.X + UDLRx[i.Rule[i.Dir - 1][j] - 1];
                    int Fy = i.Y + UDLRy[i.Rule[i.Dir - 1][j] - 1];
                    if (Fx < 0 || Fx >= N || Fy < 0 || Fy >= N)
                        continue;
 
                    if (Map[Fx][Fy].first == i.Num)
                    {
                        i.X = Fx;
                        i.Y = Fy;
                        i.Dir = i.Rule[i.Dir - 1][j];
                        break;
                    }
                }
            }
        }
 
        //모든 좌표의 냄새 유효시간 감소
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
            {
                if (Map[i][j].second == 1)
                    Map[i][j].first = 0;
 
                if (Map[i][j].second != 0)
                    Map[i][j].second--;
            }
 
        //이동한 결과를 다시 순회하며 적용. 이때 중복은 삭제.
        vector<Shark>::iterator iter = SharkVec.begin();
        for (;iter != SharkVec.end();)
        {
            if (Map[iter->X][iter->Y].second == K)
            {
                iter = SharkVec.erase(iter);
                continue;
            }
 
            Map[iter->X][iter->Y].first = iter->Num;
            Map[iter->X][iter->Y].second = K;
            iter++;
        }
 
    }
 
    cout << Time;
}

특이점은 상어들이 동시에 진행하는 판정이기 때문에, 상어들만 먼저 이동규칙에 따라서 상어 클래스 내부의 xy를 변경해주고, 이후에 상어들을 모두 담은 벡터를 순회하며 맵에 이동결과를 적용시켜준다. 또한, 이때 상어들의 위치가 중복되었다면 순번이 더 큰 상어들은 erase를 통하여 삭제시켜준다.