[백준 19237] 어른 상어 (C++)

문제 링크: www.acmicpc.net/problem/19237

19237번: 어른 상어

1. 주의할 점

- 순서대로 구현을 정확히 한다

- While문을 돌때마다 초기화를 잘 수행한다

- While문의 종료조건을 명확히 설정한다

- 매 TC마다 전역변수를 초기화한다 → 실제 시험에선 초기화한다

- 최대한 1시간이내로 풀려고 한다

 

2. 구현

- Info 구조체를 통해 상어에 대한 정보를 Shark[]에 담는다

- Info2 구조체를 통해 향수에 대한 정보를 Arr[][]에 담는다

- 이외의 배열들은 아래 주석 참고

- Make_flv() 함수를 통해 각 상어가 살아 있는 경우, 현재 자리에 자신의 향수를 남기는 과정을 수행한다

- Dev_flv() 함수를 통해 향수의 수명을 1씩 줄이며, 수명이 0이되면 해당 자리를 초기화한다

- CheckFin() 함수를 통해 1번 상어를 제외한 모든 상어가 죽거나 쫓겨났다면 True를 반환한다

- Mv_shark() 함수를 통해 죽이 않은 상어에 대해 움직임 or 정지를 수행한다. 이동된 자리에 여러마리의 상어가 존재하는 경우, AfterShkMv[][] 함수를 통해 번호가 적은 상어를 제외하곤 쫓겨나도록 설정한다

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct info{       //상어에 대한 정보
    int x,y,dir;
    bool dead = false;
};
struct info2{
    int snum,len=0;     //향수에 대한 정보
};
info tmp;

info shark[401];
int spd[401][5][4];     //[각 상어가][특정 방향일 때][상어의 탐색 방향 우선순위]
int num,sNum,len,val;
info2 arr[20][20];       //배열에서 향수에 대한 정보
int afterShkMv[20][20];        //상어가 움직인 뒤 -> 겹쳤을 때 대비해서 사용
int dx[5]={0,0,0,-1,1}; //상하좌우
int dy[5]={0,-1,1,0,0};
int curTime = 0;

void make_flv(){
    for(int k=1;k<=sNum;k++){
        if(shark[k].dead) continue;     //죽은 경우 무시
        arr[shark[k].y][shark[k].x].len = len;
        arr[shark[k].y][shark[k].x].snum = k;
    }
}

void mv_shark(){
    //초기화
    for(int i=0;i<num;i++)
        for(int j=0;j<num;j++)
            afterShkMv[i][j]=0;
        
    int cx,cy,cd,nx,ny,nd;
    for(int k=1;k<=sNum;k++){
        if(shark[k].dead) continue;     //죽은 경우 무시
        int ownFlavor=-1;
        cx = shark[k].x;
        cy = shark[k].y;
        cd = shark[k].dir;
        bool moved = false;
        for(int i=0;i<4;i++){
            nd = spd[k][cd][i];
            nx = cx + dx[nd];
            ny = cy + dy[nd];
            if(nx>=0 && ny>=0 && nx<num && ny<num){
                if(arr[ny][nx].len==0){     //향이 없는 칸
                    shark[k].x = nx;
                    shark[k].y = ny;
                    shark[k].dir = nd;
                    moved = true;
                    break;
                }
                else{       //향이 있는 칸
                    if(arr[ny][nx].snum == k && ownFlavor==-1){      //자기 자신의 향수
                        ownFlavor = nd;
                    }
                }
            }
        }
        if(!moved && ownFlavor!=-1){        //자기 자신의 향수로 갈 수 있는 경우
            nx = cx + dx[ownFlavor];
            ny = cy + dy[ownFlavor];
            shark[k].x = nx;
            shark[k].y = ny;
            shark[k].dir = ownFlavor;
        }
    }
    
    //겹치는 경우 쫓겨남 표시
    for(int k=1;k<=sNum;k++){
        if(shark[k].dead) continue;     //죽은 경우 무시
        cx = shark[k].x;
        cy = shark[k].y;
        if(afterShkMv[cy][cx]!=0) shark[k].dead = true;
        else
            afterShkMv[cy][cx] = k;
    }
}

void dec_flv(){
    for(int i=0;i<num;i++)
        for(int j=0;j<num;j++){
            if(arr[i][j].len>0){
                if(arr[i][j].len==1){
                    arr[i][j].len = 0;
                    arr[i][j].snum = 0;
                }
                else arr[i][j].len-=1;
            }
        }
}

bool checkFin(){
    bool allDied = true;
    for(int i=2;i<=sNum;i++)
        if(!shark[i].dead){
            allDied = false;
            break;
        }
    return !shark[1].dead & allDied;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >>num>>sNum>>len;
    for(int i=0;i<num;i++)
        for(int j=0;j<num;j++){
            cin>>val;
            if(val!=0){
                arr[i][j].snum = val;
                shark[val].x = j;
                shark[val].y = i;
            }
        }
    for(int i=1;i<=sNum;i++)
        cin>>shark[i].dir;
    for(int i=1;i<=sNum;i++)
        for(int j=1;j<5;j++)
            for(int k=0;k<4;k++)
                cin>>spd[i][j][k];

    while(curTime<1001){
        curTime++;
        make_flv();
        mv_shark();
        dec_flv();
        if(checkFin())  break;
    }
    curTime>1000 ? cout << -1 : cout<<curTime; 
    return 0;
}